Description

Fish is a fish that lives in the sea. One day he was bored, so he picked up trash that humans had thrown into the sea, planning to play with it.

From the pile of trash he found many matchsticks, and he used them to form a base-10 number of length $n$. Each digit is assembled as shown in the figures below.

Note: The width and placement of each digit are fixed, so the following cases are all invalid.

After finishing, he was exhausted and felt he could not build anymore. He was not satisfied with the number he formed and wanted to make it as large as possible by moving some matchsticks.

Because he is too tired, he can move at most $k$ matchsticks. Also, since the least significant digit is against a wall, he cannot append digits to the low end of the number; however, he may prepend digits to the front of the number.

Can you help him compute the maximum possible number after he moves the matchsticks?

Note: Matchsticks are precious to Fish, so breaking or discarding matchsticks is not allowed.

Note: The orientation of a match head does not affect digit recognition. For example, the following are all the digit 1.

Input Format

The input contains a single line with a base-10 number $x$ of length $n$ and an integer $k$, the maximum number of matchsticks that may be moved. The number $x$ has no leading zero.

Output Format

Output a single line containing the maximum possible number after moving the matchsticks.

3 2

17

3 3

71

Hint

For 30% of the testdata, $1 \le n \le 10$, $0 \le k \le 10$.

For 100% of the testdata, $1 \le n \le 500$, $0 \le k \le 3500$.

Translated by ChatGPT 5