Description

Xiao N is the administrator of a vegetable warehouse, responsible for designing a sales plan for the vegetables.

There are $n$ types of vegetables stored in the warehouse. Xiao N needs to design a reasonable sales plan by considering various factors based on the characteristics of different vegetables, in order to obtain the maximum profit.

When calculating the profit from selling vegetables, for each unit of the $i$-th vegetable sold, a profit of $a_i$ is obtained.

In particular, due to policies that encourage diversified sales, the first time the $i$-th vegetable is sold, an additional bonus profit of $s_i$ is also obtained.

At the beginning of operations, the inventory of the $i$-th vegetable is $c_i$ units.

However, vegetables have a very limited freshness period. Once spoiled, they cannot be sold. Fortunately, Xiao N has already calculated the spoilage time of each unit of vegetable: for the $i$-th vegetable, there exists a freshness parameter $x_i$. At the end of each day, $x_i$ units of this vegetable will spoil, until all units have spoiled. (Note: The spoilage time of each unit is fixed and does not change due to sales.)

Formally: for every positive integer $d$ such that $d \times x_i \leq c_i$, there will be $x_i$ units of the $i$-th vegetable spoiling at the end of day $d$.

In particular, if $(d - 1) \times x_i \leq c_i < d \times x_i$, then $c_i - (d - 1) \times x_i$ units of the $i$-th vegetable will spoil at the end of day $d$.

Note that when $x_i = 0$, it means this vegetable never spoils.

Meanwhile, the total number of vegetables that can be sold per day is limited to at most $m$ units.

Now, Xiao N has $k$ questions and asks for your help. Each question is: given $p_j$, if sales last for $p_j$ days, what is the maximum profit that can be obtained?

Input Format

The first line contains three positive integers $n, m, k$, representing the number of vegetable types, the maximum total number of vegetable units that can be sold per day, and the number of questions asked by Xiao N, respectively.

The next $n$ lines each contain four non-negative integers describing the characteristics of one type of vegetable, in the order $a_i, s_i, c_i, x_i$, with meanings as described above.

The next $k$ lines each contain one non-negative integer $p_j$, with the meaning as described above.

Output Format

Output $k$ lines. The number on the $i$-th line is the answer to the $i$-th question.

2 3 2
3 3 3 3
2 5 8 3
1
3

16
27

Hint

Sample Explanation

There are two types of vegetables:

For the $1$-st vegetable, the profit per unit sold is $3$, and an additional bonus profit of $3$ is obtained when selling this vegetable for the first time. There are $3$ units in total, and all of them will spoil at the end of day $1$.

For the $2$-nd vegetable, the profit per unit sold is $2$, and an additional bonus profit of $5$ is obtained when selling this vegetable for the first time. There are $8$ units in total, among which $3$ units spoil at the end of day $1$, $3$ units spoil at the end of day $2$, and $2$ units spoil at the end of day $3$.

If sales last for $1$ day, you should sell $2$ units of the first vegetable and $1$ unit of the second vegetable.

In this case: the profit from selling the first vegetable is $2 \times 3 + 3$; the profit from selling the second vegetable is $1 \times 2 + 5$; the total profit is $(2 \times 3 + 3) + (1 \times 2 + 5) = 16$.

If sales last for $3$ days, on day $1$ you should sell $3$ units of the first vegetable, on day $2$ you should sell $3$ units of the second vegetable (choose the $3$ units that will spoil at the end of day $2$), and on day $3$ you should sell $2$ units of the second vegetable.

In this case: the profit from selling the first vegetable is $3 \times 3 + 3$; the profit from selling the second vegetable is $(3 + 2) \times 2 + 5$; the total profit is $(3 \times 3 + 3) + [(3 + 2) \times 2 + 5] = 27$.

Constraints

::cute-table{tuack} | Test point ID | $n$ | $m$ | $p_j$ | Feature $1$ | Feature $2$ | | :-----------: | :---------: | :-------: | :--------: | :---------: | :---------------: | | $1$ | $\le 2$ | $\le 10$ | $\le 10^3$ | No | No | | $2$ | $\le 3$ | ^ | ^ | ^ | ^ | | $3$ | $\le 4$ | ^ | ^ | ^ | ^ | | $4$ | $\le 10^3$ | ^ | $\le 2$ | ^ | ^ | | $5$ | ^ | ^ | $\le 3$ | ^ | ^ | | $6$ | ^ | ^ | $\le 4$ | ^ | ^ | | $7$ | $\le 4$ | $\le 1$ | ^ | ^ | ^ | | $8$ | $\le 6$ | $\le 2$ | $\le 6$ | ^ | ^ | | $9$ | $\le 8$ | $\le 1$ | $\le 8$ | ^ | ^ | | $10$ | $\le 10$ | $\le 2$ | $\le 10$ | ^ | ^ | | $11$ | $\le 20$ | $\le 3$ | $\le 20$ | ^ | ^ | | $12$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | Yes | ^ | | $13$ | ^ | ^ | ^ | No | Yes | | $14$ | ^ | ^ | ^ | ^ | No | | $15$ | ^ | ^ | ^ | ^ | ^ | | $16$ | $\le 10^3$ | ^ | $\le 10^3$ | Yes | Yes | | $17$ | ^ | ^ | ^ | ^ | No | | $18$ | ^ | ^ | ^ | No | Yes | | $19$ | ^ | ^ | ^ | ^ | No | | $20$ | ^ | ^ | ^ | ^ | ^ | | $21$ | $\le 10^5$ | ^ | $\le 10^5$ | Yes | Yes | | $22$ | ^ | ^ | ^ | ^ | No | | $23$ | ^ | ^ | ^ | No | Yes | | $24$ | ^ | ^ | ^ | ^ | No | | $25$ | ^ | ^ | ^ | ^ | ^ |

Feature $1$: all $s_i$ are $0$.

Feature $2$: all $x_i$ are $0$.

For all testdata, it is guaranteed that the $p_j$ in the $k$ queries are pairwise distinct.

For all testdata, it is guaranteed that $0 < a_i, c_i \le 10^9$, $0 \le s_i, x_i \le 10^9$.

Translated by ChatGPT 5