问题 C: 数字替换

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:68 通过:36

题目描述

味味很喜欢玩一个数字替换的游戏,数字替换游戏是这样的:给出一个 n 位正整数 a, 然后再给你一个长度为 m 的数字序列 b,味味可以用 b 中的一些数字与 a 中各个位置上的 数字进行一对一的交换(当然也可以选择不交换)。当然 b 中的每个位置上的数字最多只能 被使用一次。这个游戏的目的是经过一系列替换后,使 a 的数值达到最大。
味味很聪明,在位数不多的情况下,总能快速的求出最后 a 的最大数值,但是当 n 很 大时,味味就无能为力了,所以她希望会写程序的你帮助她快速的求解 a 最后能到达的那 个最大值。

输入格式

输入共包含三行。第一行两个用空格隔开的正整数 n,m。第二行一个正整数 a(a 的最高位必定不是 0)。第三行一个长度为 m 的数字序列 b。


b 中的一个 1 和 a 中的第二位上的 0 进行交换。

对于 20%的数据 1≤n,m≤10 
对于 50%的数据 1≤n,m≤2000 
对于 100%的数据 1≤n,m≤100000

输出格式

输出仅包含一行一个数值,表示 a 最大可能达到的数值(输出不能含前导0)。

输入样例 复制

4 3
1024
010

输出样例 复制

1124

数据范围与提示

b 中的一个 1 和 a 中的第二位上的 0 进行交换。

对于 20%的数据 1≤n,m≤10 
对于 50%的数据 1≤n,m≤2000 
对于 100%的数据 1≤n,m≤100000