169B.md (1408B)
1 Source: https://codeforces.com/problemset/problem/169/B 2 3 B. Replacing Digits 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 You are given an integer *a* that consists of *n* digits. You are also given a sequence of digits *s* of length *m*. The digit in position *j* (1 ≤ *j* ≤ *m*) of sequence *s* means that you can choose an arbitrary position *i* (1 ≤ *i* ≤ *n*) in *a* and replace the digit in the chosen position *i* with *s**j*. Each element in the sequence *s* can participate in no more than one replacing operation. 22 23 Your task is to perform such sequence of replacements, that the given number *a* gets maximum value. You are allowed to use not all elements from *s*. 24 25 Input 26 27 The first line contains positive integer *a*. Its length *n* is positive and doesn't exceed 105. The second line contains sequence of digits *s*. Its length *m* is positive and doesn't exceed 105. The digits in the sequence *s* are written consecutively without any separators. 28 29 The given number *a* doesn't contain leading zeroes. 30 31 Output 32 33 Print the maximum value that can be obtained from *a* after a series of replacements. You are allowed to use not all elements from *s*. The printed number shouldn't contain any leading zeroes. 34 35 Examples 36 37 Input 38 39 ``` 40 1024 41 010 42 ``` 43 44 Output 45 46 ``` 47 1124 48 ``` 49 50 Input 51 52 ``` 53 987 54 1234567 55 ``` 56 57 Output 58 59 ``` 60 987 61 ```