Knapsack

## 题目描述 你有一个容量为$W$的背包，和$8$种物品，重量分别为$1$~$8$的整数，分别有$cnt_1,cnt_2...cnt_8$个。 求背包中最多能装上多大的重量。 ## 输入输出格式 ### 输入格式： 第一行一个整数$W$，表示背包容量。 第二行有$8$个整数$cnt_1,cnt_2...cnt_8$，其中$cnt_i$表示重量为$i$的物品数量。 ### 输出格式： 一个整数，表示背包中最多能装的重量。 ## 说明 ### 数据范围： $0\le W \le10^{18}$ $0 \le cnt_i \le 10^{16}$

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.

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.

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

10
1 2 3 4 5 6 7 8

10

0
0 0 0 0 0 0 0 0

0

3
0 4 1 0 0 9 8 3

3