/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
高橋君は整数 x を持っています。最初 x=0 です。
高橋君は以下の操作を好きな回数行えます。
- 整数 i\ (1\leq i \leq 9) を選ぶ。 C_i 円払い、x を 10x + i で置き換える。
高橋君の予算は N 円です。操作で支払うお金の総和が予算を超過しないように操作を行うとき、最終的に得られる x の最大値を求めてください。
制約
- 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
例えば i = 9 とする操作、i=5 とする操作を順に行うことで、x は以下のように変化します。
0 \rightarrow 9 \rightarrow 95
操作により支払うお金の合計は C_9 + C_5 = 3 + 2 = 5 円であり、これは予算を超過しません。 予算を超過しないような操作の方法によって 96 以上の整数を作ることが不可能であることが証明できるので、答えは 95 です。
入力例 2
20 1 1 1 1 1 1 1 1 1
出力例 2
99999999999999999999
答えが 64 bit整数型に収まらないこともあることに注意してください。
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
Output
Print the answer.
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.