For \(k=1,2,\ldots,9\), let \(C_k\) be the number of occurrences of the digit \(k\) in \(T\).

By thinking about the operations in reverse, the entire sequence of operations can be restated as follows:

• For each \(x=1,2,\ldots,9\), you can perform an operation that replaces any position in \(S\) with \(x\) at most \(C_x\) times. … \(\text{(A)}\)
• However, you must perform at least one operation that replaces a position with \(T_M\). … \(\text{(B)}\)

First, ignore condition \(\text{(B)}\) and consider only condition \(\text{(A)}\). We want to find the maximum possible value of \(S\) after performing operations under \(\text{(A)}\) alone.

It can be seen that the following greedy procedure is optimal:

• For \(k=1,2,\ldots,N\), do:
  • Let \(X\) be the largest integer \(x\) such that \(S_k < x \le 9\) and \(C_x \geq 1\). Then, replace \(S_k\) with \(X\) and decrease \(C_X\) by \(1\). If there is no such \(x\), do nothing.

Let \(S'\) be the string obtained by this process. Next, consider how much the final answer is reduced once we add condition \(\text{(B)}\).

If \(S'\) already contains the character \(T_M\), then:

• If you have already used \(T_M\) in your operations, condition \(\text{(B)}\) is satisfied.
• If you have not used \(T_M\) yet, you can perform an operation on the position where \(S'\) has \(T_M\), satisfying condition \(\text{(B)}\).

In either case, the answer remains \(S'\).

Conversely, if \(S'\) does not contain the character \(T_M\), then you must overwrite some position of \(S'\) with \(T_M\). The position that reduces the value the least is \(S'_N\).

By implementing this logic appropriately, you can solve the problem. The complexity is \(O(N+M)\).

Sample Implementation (Python3)

n, m = map(int, input().split())
S = [int(c) for c in input()]
T = [int(c) for c in input()]
cnt = [T.count(i) for i in range(10)]
for i in range(n):
    for j in range(9, S[i], -1):
        if cnt[j] > 0:
            cnt[j] -= 1
            S[i] = j
            break
if not T[-1] in S:
    S[-1] = T[-1]
print("".join(map(str, S)))