Electronic Lock

Interview

Time limit2sMemory limit1024 MB

Summary

Find the largest integer without leading zeros that uses exactly n lit segments, with digits drawn only from the given set.

Level: Medium5 of 10
Topics: Dynamic programming, Greedy
Solved: No attempts yet

Statement

Kowalski decided to build an electronic lock for his new invention. The lock is a sequence of 7-segment displays. There is no full keypad, so only some digits can be used in the password. The password is an integer without leading zeros.

Kowalski cannot read, but he can count. He wants exactly $n$ segments to light up when the password is entered. A segment is one of the unit line segments that make up a 7-segment display. Among all passwords that fit, he wants the largest one.

Fig. 1: How each digit is shown on a 7-segment display.

Help Kowalski find the number. At least one valid password is guaranteed to exist.

Input

The first line contains two integers $n$ and $m$ , where $n$ is the required number of lit segments and $m$ is the number of available digits ( $2 \le n \le 100\,000$ , $1 \le m \le 10$ ). The second line contains the $m$ available digits in increasing order.

Output

Print one number, the required password. It must not have leading zeros. At least one valid password is guaranteed to exist.

Hint

In the first example, exactly 7 segments must light up, so Kowalski must use 8 as the password.

Examples3

Example 1
Input
```
7 8
0 2 3 4 5 6 8 9
```
Expected output
```
8
```
Example 2
Input
```
6 1
0
```
Expected output
```
0
```
Example 3
Input
```
15 8
0 2 3 4 5 6 8 9
```
Expected output
```
954
```