E. 最小字符串

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

给定一个长度为 $N$ 且只包含小写字母的字符串 $S$ ，和 $M$ 个小写字母 $c_1,c_2,...,c_M$ 。现在你要把 $M$ 个小写字母全部插入到字符串 $S$ 中，每个小写字母都可以插入到任意位置。请问能得到的字典序最小的字符串是什么？

第一行包含两个整数 $N$ 和 $M$ 。第二行包含一个长度为 $N$ 的字符串 $S$ 。第三行包含 $M$ 个小写字母 $c_1,c_2,...,c_M$ 。

输出一个长度为 $N+M$ 的字符串代表答案。

4 3
abbc
cba

aabbbcc

7 3
lanqiao
bei

beilanqiao

对于 $20\%$ 的评测用例， $M=1$ 。

对于 $100\%$ 的评测用例， $1≤N,M≤10^5$ 。