Problem Description

Fish is a fish living in the sea. One day, he was very bored, so he picked up some trash thrown by humans into the sea and decided to play with it.

Among the trash he collected, he found many matchsticks and used them to form a decimal number of length \( n \). The way each digit is formed is shown in the figure below.

Note: Each digit occupies a fixed width and placement, so the following cases are not valid.

After forming the number, he was very tired and felt he wouldn't do it again. He was dissatisfied with the size of the number and wanted to move some matchsticks to make the number as large as possible.

Since he was too tired, he could move at most \( k \) matchsticks. Also, since the lowest digit was placed against a wall, he could not add digits after the lowest digit, but he could add digits in front of the number.

Can you help him calculate the maximum number he can achieve after moving the matchsticks?

Note: Matchsticks are precious to Fish, so it is not allowed to break or discard them.

Note: The direction of the matchstick heads does not affect the recognition of the digits, for example, the following cases are all digit 1.

Input Format

The input consists of a single line containing the decimal number \( x \) of length \( n \) and the maximum number of matchsticks \( k \) that can be moved. \( x \) does not have leading zeros.

Output Format

Output a single line representing the maximum number after moving the matchsticks.

Sample Input and Output

Sample Input #1

3 2

Sample Output #1

17

Sample Input #2

3 3

Sample Output #2

71

Notes/Hints

For 30% of the data, \( 1 \leq n \leq 10 \), \( 0 \leq k \leq 10 \).

For 100% of the data, \( 1 \leq n \leq 500 \), \( 0 \leq k \leq 3500 \).

见题面 Input 部分

见题面 Output 部分