Problem 22181 --数字替换

22181: 数字替换

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 21  Solved: 11
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][20kb]

Description

  

味味很喜欢玩一个数字替换的游戏,数字替换游戏是这样的:给出一个n位正整数a,然后再给你一个长度为m的数字序列b,味味可以用b中的一些数字与a中各个位置上的数字进行一对一的交换(当然也可以选择不交换)。当然b中的每个位置上的数字最多只能被使用一次。这个游戏的目的是经过一系列替换后,使a的数值达到最大。

味味很聪明,在位数不多的情况下,总能快速的求出最后a的最大数值,但是当n很大时,味味就无能为力了,所以她希望会写程序的你帮助她快速的求解a最后能到达的那个最大值。

Input

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

Output

 

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

Sample Input

4 3
1024
010

Sample Output

1124

HINT

 


【数据范围】



对于20%的数据  1nm10



对于 50%的数据  1nm2000



对于100%的数据1nm100000




Source

[Submit][Status]