加法与乘法 2

题目描述

高桥君有一个整数 $x$。初始时 $x=0$。

高桥君可以任意次执行以下操作。

选择整数 $i\ (1 \le i \le 9)$。支付 $C_i$ 日元，把 $x$ 替换为 $10x + i$。

高桥君有 $N$ 日元的预算。求在不超出预算的前提下，最终 $x$ 的最大可能值。

输入格式

输入按以下格式从标准输入给出：

N
C_1 C_2 … C_9

输出格式

输出答案。

样例

5
5 4 3 3 2 5 3 5 3

95

例如，按顺序执行 $i=9$、$i=5$ 的操作，$x$ 变化如下：

$0 \rightarrow 9 \rightarrow 95$。

这些操作所需的金额为 $C_9 + C_5 = 3 + 2 = 5$ 日元，没有超出预算。由于可以证明在不超出预算的前提下无法得到大于等于 96 的整数，因此答案是 95。

20
1 1 1 1 1 1 1 1 1

99999999999999999999

注意，答案可能超出 64 位整数类型的表示范围。

数据范围

• $1 \le N \le 10^6$
• $1 \le C_i \le N$
• 输入中的所有值均为整数。