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.

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.