Little N is a vegetable warehouse manager responsible for designing vegetable sales plans.
There are $n$ types of vegetables in the warehouse. Little N needs to design a reasonable sales plan based on the characteristics of different vegetables to maximize profit.
When calculating the profit from selling vegetables, selling one unit of the $i$-th type of vegetable yields a profit of $a_i$. Specifically, because the policy encourages diversified sales, the first time the $i$-th type of vegetable is sold, an additional profit of $s_i$ is obtained.
At the beginning of operations, the inventory of the $i$-th type of vegetable is $c_i$ units.
However, the shelf life of vegetables is very limited, and they cannot be sold once they spoil. The clever Little N has already calculated the spoilage time for each unit of vegetable: for the $i$-th type of vegetable, there is a freshness value $x_i$. At the end of each day, $x_i$ units of the vegetable will spoil, until all vegetables have spoiled. (Note: The spoilage time for each unit of vegetable is fixed and does not change with sales.)
Formally: For all positive integers $d$ satisfying $d \times x_i \le c_i$, $x_i$ units of the vegetable will spoil at the end of day $d$.
Specifically, if $(d - 1) \times x_i \le c_i < d \times x_i$, then $c_i - (d - 1) \times x_i$ units of the vegetable will spoil at the end of day $d$.
Note that when $x_i = 0$, it means this type of vegetable will not spoil.
At the same time, the total amount of vegetables that can be sold each day is also limited, not exceeding $m$ units.
Now, Little N has $k$ questions and would like your help. Each question is in the form: For a known $p_j$, if you need to sell for $p_j$ days, what is the maximum profit that can be obtained?
Input
The input is read from the file vegetables.in.
The first line contains three positive integers $n, m, k$, representing the number of vegetable types, the daily limit on the total amount of vegetables that can be sold, and the number of questions proposed by Little N, respectively.
The next $n$ lines each contain four non-negative integers describing the characteristics of a vegetable type, in the order $a_i, s_i, c_i, x_i$, with meanings as described above.
The next $k$ lines each contain a non-negative integer $p_j$, with the meaning as described above.
Output
The output is written to the file vegetables.out.
Output $k$ lines, each containing an integer, where the $i$-th line represents the answer to the $i$-th question.
Examples
Input 1
2 3 2 3 3 3 3 2 5 8 3 1 3
Output 1
16 27
Note 1
There are two types of vegetables: For the 1st type of vegetable, the profit per unit sold is 3, and the first sale of this vegetable yields an additional profit of 3. There are 3 units of this vegetable in total, all of which spoil at the end of the first day. For the 2nd type of vegetable, the profit per unit sold is 2, and the first sale of this vegetable yields an additional profit of 5. There are 8 units of this vegetable in total, of which 3 units spoil at the end of the first day, 3 units spoil at the end of the second day, and 2 units spoil at the end of the third day.
When selling for only 1 day, one should sell 2 units of the first type of vegetable and 1 unit of the second type of vegetable. In this case: the profit from selling the first type of vegetable is $2 \times 3 + 3$; the profit from selling the second type of vegetable is $1 \times 2 + 5$; the total profit obtained is $(2 \times 3 + 3) + (1 \times 2 + 5) = 16$.
When selling for 3 days, on the first day one should sell 3 units of the first type of vegetable, on the second day one should sell 3 units of the second type of vegetable (choosing the 3 units that spoil at the end of the second day), and on the third day sell 2 units of the second type of vegetable. In this case: the profit from selling the first type of vegetable is $3 \times 3 + 3$; the profit from selling the second type of vegetable is $(3 + 2) \times 2 + 5$; the total profit obtained is $(3 \times 3 + 3) + [(3 + 2) \times 2 + 5] = 27$.
Subtasks
| Test Case ID | $n$ | $m$ | $p_j$ | Characteristic 1 | Characteristic 2 |
|---|---|---|---|---|---|
| 1 | $\le 2$ | $\le 10$ | $\le 10^3$ | None | None |
| 2 | $\le 3$ | $\le 10$ | $\le 10^3$ | None | None |
| 3 | $\le 4$ | $\le 10$ | $\le 10^3$ | None | None |
| 4 | $\le 10^3$ | $\le 10$ | $\le 2$ | None | None |
| 5 | $\le 3$ | $\le 10$ | $\le 3$ | None | None |
| 6 | $\le 4$ | $\le 10$ | $\le 4$ | None | None |
| 7 | $\le 4$ | $\le 1$ | $\le 10^3$ | None | None |
| 8 | $\le 6$ | $\le 2$ | $\le 6$ | None | None |
| 9 | $\le 8$ | $\le 1$ | $\le 8$ | None | None |
| 10 | $\le 10$ | $\le 2$ | $\le 10$ | None | None |
| 11 | $\le 20$ | $\le 3$ | $\le 20$ | None | None |
| 12 | $\le 10^2$ | $\le 10$ | $\le 10^2$ | Yes | No |
| 13 | $\le 10^2$ | $\le 10$ | $\le 10^2$ | No | Yes |
| 14 | $\le 10^2$ | $\le 10$ | $\le 10^2$ | No | No |
| 15 | $\le 10^2$ | $\le 10$ | $\le 10^2$ | No | No |
| 16 | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Yes | Yes |
| 17 | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Yes | No |
| 18 | $\le 10^3$ | $\le 10$ | $\le 10^3$ | No | Yes |
| 19 | $\le 10^3$ | $\le 10$ | $\le 10^3$ | No | No |
| 20 | $\le 10^3$ | $\le 10$ | $\le 10^3$ | No | No |
| 21 | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Yes | Yes |
| 22 | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Yes | No |
| 23 | $\le 10^5$ | $\le 10$ | $\le 10^5$ | No | Yes |
| 24 | $\le 10^5$ | $\le 10$ | $\le 10^5$ | No | No |
| 25 | $\le 10^5$ | $\le 10$ | $\le 10^5$ | No | No |
Characteristic 1: All $s_i$ are 0. Characteristic 2: All $x_i$ are 0.
For all test data, it is guaranteed that the $p_j$ in the $k$ queries are distinct. For all test data, it is guaranteed that $0 < a_i, c_i \le 10^9$ and $0 \le s_i, x_i \le 10^9$.