Exact Volume Complete Knapsack Problem

In this problem, you are given a complete knapsack problem. There are \(n\) types of items, where the \(i\)-th item has a volume of \(v_i\) and a value of \(c_i\). You are then given \(q\) queries. For each query, you are provided with a knapsack capacity \(V\). Your task is to select any number (possibly zero) of each item such that the total volume is exactly \(V\) and the total value is maximized. If it is impossible to reach exactly volume \(V\) using the available items, you should output \(-1\).

Note: To illustrate your ability to solve NP-hard problems, \(V\) can be significantly larger than the individual volumes \(v_i\). However, the test cases provided will be of moderate size.

inputFormat

The first line contains two space-separated integers \(n\) and \(q\) (e.g. \(1 \le n \le 100\), \(1 \le q \le 10^5\)), representing the number of item types and the number of queries respectively.

The following \(n\) lines each contain two space-separated integers \(v_i\) and \(c_i\) (e.g. \(1 \le v_i \le 10^6\), \(1 \le c_i \le 10^6\)), representing the volume and value of the \(i\)-th item.

The next \(q\) lines each contain a single integer \(V\) (e.g. \(1 \le V \le 10^{12}\)), denoting the capacity for that query.

outputFormat

For each query, output the maximum total value achievable with exactly volume \(V\). If no valid combination exists, output -1.

sample

3 3
2 3
3 4
4 5
5
7
11

7
11
-1