CF1132E.Knapsack

You have a set of items, each having some integer weight not greater than $8$. You denote that a subset of items is good if total weight of items in the subset does not exceed $W$.

You want to calculate the maximum possible weight of a good subset of items. Note that you have to consider the empty set and the original set when calculating the answer.

你有一组物品，每个物品的重量均为不超过 $8$ 的整数。我们称一个物品子集为“好”的，当且仅当该子集中所有物品的总重量不超过 $W$。

你需要计算一个“好”子集所能达到的最大可能总重量。注意：在计算答案时，必须考虑空集以及原始全集。

The first line contains one integer $W$ ($0 \le W \le 10^{18}$) — the maximum total weight of a good subset.

The second line denotes the set of items you have. It contains $8$ integers $cnt_1$, $cnt_2$, ..., $cnt_8$ ($0 \le cnt_i \le 10^{16}$), where $cnt_i$ is the number of items having weight $i$ in the set.

第一行包含一个整数 $W$（$0 \le W \le 10^{18}$）—— 表示一个优质子集的最大总重量。

第二行描述你所拥有的物品集合。它包含 $8$ 个整数 $cnt_1$, $cnt_2$, ..., $cnt_8$（$0 \le cnt_i \le 10^{16}$），其中 $cnt_i$ 表示集合中重量为 $i$ 的物品的数量。

Print one integer — the maximum possible weight of a good subset of items.

输出一个整数——好物品子集的最大可能重量。