102574: [AtCoder]ABC257 E - Addition and Multiplication 2

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.

问题描述

高桥有一个整数$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$位整数类型中。