Contest Duration: - (local time) (100 minutes) Back to Home
E - Addition and Multiplication 2 /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• 整数 i\ (1\leq i \leq 9) を選ぶ。 C_i 円払い、x10x + i で置き換える。

### 制約

• 1 \leq N \leq 10^6
• 1 \leq C_i \leq N
• 入力は全て整数

### 入力

N
C_1 C_2 \ldots C_9

### 入力例 1

5
5 4 3 3 2 5 3 5 3

### 出力例 1

95

0 \rightarrow 9 \rightarrow 95

### 入力例 2

20
1 1 1 1 1 1 1 1 1

### 出力例 2

99999999999999999999

Score : 500 points

### Problem Statement

Takahashi has an integer x. Initially, x=0.

Takahashi may do the following operation any number of times.

• Choose an integer i\ (1\leq i \leq 9). Pay C_i yen (the currency in Japan) to replace x with 10x + i.

Takahashi has a budget of N yen. Find the maximum possible value of the final x resulting from operations without exceeding the budget.

### Constraints

• 1 \leq N \leq 10^6
• 1 \leq C_i \leq N
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N
C_1 C_2 \ldots C_9

### Sample Input 1

5
5 4 3 3 2 5 3 5 3

### Sample Output 1

95

For example, the operations where i = 9 and i=5 in this order change x as:

0 \rightarrow 9 \rightarrow 95.

The amount of money required for these operations is C_9 + C_5 = 3 + 2 = 5 yen, which does not exceed the budget. Since we can prove that we cannot make an integer greater than or equal to 96 without exceeding the budget, the answer is 95.

### Sample Input 2

20
1 1 1 1 1 1 1 1 1

### Sample Output 2

99999999999999999999

Note that the answer may not fit into a 64-bit integer type.