Score : $500$ points

问题描述

Takahashi 拥有一个整数 $x$。最初，$x=0$。

Takahashi 可以任意多次执行以下操作：

• 选择一个整数 $i\ (1\leq i \leq 9)$。花费 $C_i$ 日元（日本货币）将 $x$ 替换为 $10x + i$。

Takahashi 的预算是 $N$ 日元。在不超过预算的情况下，找出通过操作得到的最终 $x$ 值的最大可能值。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 10:55:36