Addition and Multiplication 2

题目描述

Takahashi 有一个整数 $x$。 起初，$x=0$。 Takahashi 可以任意次数执行以下操作。

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

Takahashi 有预算 $N$ 日元。 在不超过预算的情况下，求最终 $x$ 的最大可能值。

输入格式

输入按下列格式从标准输入给出： $N$ $C_1$ $C_2$ $\ldots$ $C_9$

输出格式

输出答案。

5
5 4 3 3 2 5 3 5 3

95

20
1 1 1 1 1 1 1 1 1

99999999999999999999

提示

$1 \leq N \leq 10^6$ $1 \leq C_i \leq N$ 输入中的所有值均为整数。例如，依次进行 $i = 9$ 和 $i=5$ 的操作会使 $x$ 变为： $0 \rightarrow 9 \rightarrow 95$。
这些操作所需的金额为 $C_9 + C_5 = 3 + 2 = 5$ 日元，不超过预算。 由于可以证明在不超过预算的情况下无法得到大于等于 $96$ 的整数，答案为 $95$。
注意答案可能无法放入 64 位整数类型。

标签: AtCoder|abc257E

来源

AtCoder|abc257E