P9140 [THUPC 2023 Preliminary] Knapsack

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.

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.

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.

#### 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 . Translated by ChatGPT 5