当前没有测试数据。

E - 加法和乘法 2

分数: 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$

输出

输出答案。

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 位整数类型。