Digital Display

Time limit5sMemory limit1024 MB

Summary

Given a number shown on a seven-segment display, move at most K sticks between digits to form the smallest larger number, or report that none exists.

Level: Medium6 of 10
Topics: Greedy, Implementation, String
Solved: No attempts yet

Problem

Smart boy Vasya is a beginner mathematician. Today is his birthday, and many guests bring gifts as usual. His best friend Vovochka gave him an unusual present: a device with a digital display. It shows an $N$ -digit number $X$ using $N$ indicators made of seven segments each.

The device looks much like an electronic clock, but instead of the usual format it shows time as seconds since some very important moment. That was so long ago that Vovochka does not remember which important event took place when he first switched the device on.

Vovochka told Vasya that the clock can tell when the next important event will happen. To find out, take the number currently on the display and rearrange at most $K$ sticks to get the smallest number greater than it. Sticks may be moved from one digit to another. Vovochka has planned this gift for a long time and has already calculated the moment when he will tell Vasya.

Vasya is not as good at math as Vovochka, so he asks you to write a program that answers his question.

Input

The first line contains an integer $K$ ( $1 \le K \le 100$ ). The second line contains the number $X$ ( $0 \le X < 10^{100000}$ ).

Output

Print one number: the answer to the problem, or <NO SOLUTION> if no answer exists.

Examples2

Example 1
Input
```
2
4598
```
Expected output
```
4600
```
Example 2
Input
```
3
888
```
Expected output
```
NO SOLUTION
```