Problem Description

In this problem, you need to solve the Complete Knapsack problem.

There are $n$ types of items. For item type $i$, each item has volume $v_i$ and value $c_i$.

There are $q$ queries. In each query, you are given the knapsack capacity $V$. You need to choose some items; for each type, you may choose any number of items (including choosing none). Under the constraint that the total volume of the chosen items is exactly $V$, maximize the total value of the chosen items. You need to output this maximum total value, or report that there is no way to make the total volume exactly $V$.

To show your ability to solve NP-Hard problems, $V$ will be much larger than $v_i$. See the Constraints section for details.

Input Format

The first line contains two integers $n, q$, representing the number of item types and the number of queries.

The next $n$ lines each contain two integers $v_i, c_i$, describing one type of item.

The next $q$ lines each contain one integer $V$, describing the knapsack capacity in a query.

Output Format

For each query, output one integer per line. If there is no solution whose total volume is exactly $V$, output -1; otherwise output the maximum total value of the chosen items.

2 2
6 10
8 15
100000000001
100000000002

-1
187500000000

Hint

Sample Explanation 1

For the second query, the optimal solution is: choose $3$ items of type $1$ and $12499999998$ items of type $2$.

Subtasks

For all testdata, $1 \le n \le 50, 1 \le v_i \le 10^5, 1 \le c_i \le 10^6, 1 \le q \le 10^5, 10^{11} \le V \le 10^{12}$.

Source

From the preliminary round of THUPC2023 (Tsinghua University Student Programming Contest and Intercollegiate Invitational Contest 2023).

Resources such as editorials can be found at https://github.com/THUSAAC/THUPC2023-Pre.

Translated by ChatGPT 5