/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
長さ N の文字列 S と長さ M の文字列 T が与えられます。ここで、 S,T はどちらも 1 から 9 までの数字からなります。
あなたは以下の操作を k=1,2,\ldots,M の順に行います。
- 1\le i\le N を満たす整数 i を選ぶ。そして、 S の i 文字目を T の k 文字目で置き換える。
M 回の操作が終わった後の文字列 S を整数としてみた値の最大値を求めてください。
制約
- 1\le N,M\le 10^6
- N,M は整数
- S は
1から9までの数字からなる長さ N の文字列 - T は
1から9までの数字からなる長さ M の文字列
入力
入力は以下の形式で標準入力から与えられる。
N M S T
出力
M 回の操作が終わった後の文字列 S を整数としてみた値の最大値を出力せよ。
入力例 1
3 3 191 325
出力例 1
593
以下の操作方法が最適です。
- k=1 のとき： i=3 を選ぶ。 S=
193となる。 - k=2 のとき： i=1 を選ぶ。 S=
293となる。 - k=3 のとき： i=1 を選ぶ。 S=
593となる。
この場合 S を整数としてみた値は 593 となり、これが最大です。
入力例 2
3 9 191 998244353
出力例 2
993
入力例 3
11 13 31415926535 2718281828459
出力例 3
98888976555
Score : 400 points
Problem Statement
You are given a string S of length N and a string T of length M, both consisting of digits from 1 to 9.
You will perform the following operation for k=1,2,\ldots,M in order:
- Choose an integer i such that 1 \le i \le N. Then, replace the i-th character of S with the k-th character of T.
Find the maximum possible value of the resulting string S interpreted as an integer after performing the M operations.
Constraints
- 1 \le N,M \le 10^6
- N and M are integers.
- S is a string of length N consisting of digits from
1through9. - T is a string of length M consisting of digits from
1through9.
Input
The input is given from Standard Input in the following format:
N M S T
Output
Print the maximum possible value of the resulting string S interpreted as an integer after performing the M operations.
Sample Input 1
3 3 191 325
Sample Output 1
593
The following sequence of operations is optimal:
- For k=1: Choose i=3. Then, S =
193. - For k=2: Choose i=1. Then, S =
293. - For k=3: Choose i=1. Then, S =
593.
In this case, the value of S interpreted as an integer is 593, which is the maximum.
Sample Input 2
3 9 191 998244353
Sample Output 2
993
Sample Input 3
11 13 31415926535 2718281828459
Sample Output 3
98888976555