AT_ndpc2026_n ナップサック

There are infinitely many items of each of $ N $ types. The $ i $ -th type of item has weight $ i $ and value $ v_i $ . You are given $ Q $ queries. In each query, you are given a positive integer $ W $ . Find the maximum possible total value when you choose some items such that the total weight is exactly $ W $ .

The input is given from standard input in the following format: > $ N $ $ Q $ $ v_1 $ $ v_2 $ $ \dots $ $ v_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Each query is given in the following format: > $ W $

Print $ Q $ lines. On the $ i $ -th line, output the answer for the $ i $ -th query.

### Note This problem requires more specialized knowledge compared to the others. If you do not have an idea for a full solution, it is recommended to aim for partial points and then move on to the next problem. ### Partial Score This problem has partial scoring. - If you solve the dataset with $ N \leq 300 $ , you will get $ 4 $ points. ### Sample Explanation 1 For example, in the 6th query, $ W=6 $ . If you take two items of type $ 3 $ , the total value becomes $ 7 + 7 = 14 $ , which is the maximum. ### Constraints - $ 1 \leq N \leq 4000 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 0 \leq v_i \leq 10^9 $ - $ 1 \leq W \leq 10^9 $ - All input values are integers