/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
ちょうど N 本のマッチ棒を使って作れる整数の中で最大のものを求めてください。
ただし、以下の条件を満たさなければなりません。
- 作る整数の各桁は、1 から 9 までの数字のうち A_1, A_2, ..., A_M (1 \leq A_i \leq 9) のいずれかでなければならない。
- 数字 1, 2, 3, 4, 5, 6, 7, 8, 9 を 1 つ作るには、それぞれちょうど 2, 5, 5, 4, 5, 6, 3, 7, 6 本のマッチ棒を使う。
制約
- 入力は全て整数である。
- 2 \leq N \leq 10^4
- 1 \leq M \leq 9
- 1 \leq A_i \leq 9
- A_i は全て異なる。
- ちょうど N 本のマッチ棒を使って条件を満たすように作れる整数が存在する。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 ... A_M
出力
問題文の条件下でちょうど N 本のマッチ棒を使って作れる整数の最大値を出力せよ。
入力例 1
20 4 3 7 8 4
出力例 1
777773
整数 777773 は 3 + 3 + 3 + 3 + 3 + 5 = 20 本のマッチ棒を使って作れ、ちょうど 20 本のマッチ棒を使って条件を満たすように作れる整数の中でこれが最大です。
入力例 2
101 9 9 8 7 6 5 4 3 2 1
出力例 2
71111111111111111111111111111111111111111111111111
出力が 64 ビット整数型に収まらない場合があります。
入力例 3
15 3 5 4 6
出力例 3
654
Score : 400 points
Problem Statement
Find the largest integer that can be formed with exactly N matchsticks, under the following conditions:
- Every digit in the integer must be one of the digits A_1, A_2, ..., A_M (1 \leq A_i \leq 9).
- The number of matchsticks used to form digits 1, 2, 3, 4, 5, 6, 7, 8, 9 should be 2, 5, 5, 4, 5, 6, 3, 7, 6, respectively.
Constraints
- All values in input are integers.
- 2 \leq N \leq 10^4
- 1 \leq M \leq 9
- 1 \leq A_i \leq 9
- A_i are all different.
- There exists an integer that can be formed by exactly N matchsticks under the conditions.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 ... A_M
Output
Print the largest integer that can be formed with exactly N matchsticks under the conditions in the problem statement.
Sample Input 1
20 4 3 7 8 4
Sample Output 1
777773
The integer 777773 can be formed with 3 + 3 + 3 + 3 + 3 + 5 = 20 matchsticks, and this is the largest integer that can be formed by 20 matchsticks under the conditions.
Sample Input 2
101 9 9 8 7 6 5 4 3 2 1
Sample Output 2
71111111111111111111111111111111111111111111111111
The output may not fit into a 64-bit integer type.
Sample Input 3
15 3 5 4 6
Sample Output 3
654