| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 24 | 10 | 10 | 52.632% |
Little N is the administrator of the vegetable warehouse and is responsible for designing the sales plan of vegetables.
In the vegetable warehouse, there are $n$ kinds of vegetables stored in total. Little N needs to design a reasonable sales plan based on the characteristics of different vegetables and comprehensively consider various factors to obtain the most benefits.
When calculating the income from selling vegetables, for every unit of $i$th vegetable sold, you can get $a_i$ income.
In particular, since the policy encourages merchants to conduct diversified sales, when selling the $i$th vegetable for the first time, they will also get an additional income of $s_i$.
At the start of the operation, the stock of vegetable $i$ is $c_i$ units.
However, the preservation time of vegetables is very limited, once they go bad, they cannot be sold, but the smart little N has calculated the time for each unit of vegetables to go bad: for the $i$th vegetable, there is a freshness value $x_i,ドル and there will be $x_i$ units of vegetables going bad at the end of each day, until all vegetables go bad. (Note: The spoilage time of each unit of vegetables is fixed and does not change with sales)
Formally: for all positive integers $d$ satisfying the condition $d\times x_i \leq c_i,ドル $x_i$ units of vegetables will spoil at the end of $d$ day.
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 vegetables will spoil by the end of $d$ days.
Note that when $x_i = 0,ドル it means that this vegetable will not go bad.
At the same time, the total amount of vegetables sold every day is also limited, and cannot exceed $m$ units at most.
Now, Little N has $k$ query. Each query is of the form: Given $p_j,ドル if you need to sell for $p_j$ days, what is the maximum profit you can get?
The first line contains three positive integers $n, m, k,ドル which respectively represent the number of types of vegetables, the upper limit of the total amount of vegetables that can be sold every day, and the number of questions raised by small N.
In the next $n$ lines, enter four non-negative integers in each line to describe the characteristics of a vegetable, which are $a_i, s_i, c_i, x_i$ in turn, and the meanings are as described above.
In the next $k$ lines, enter a non-negative integer $p_j$ in each line, the meaning is as described above.
Output $k$ lines, each line contains an integer, and the number in line $i$ represents the answer to question $i$.
For all test data, it is guaranteed that $p_j$ in $k$ sets of queries are different from each other.
For all test data, it is guaranteed that 0,ドル 0ドル\le s_i,x_i\le 10^9$.
2 3 2 3 3 3 3 2 5 8 3 1 3
16 27
There are two types of vegetables:
When selling the 1ドル$ vegetable, you can get 3ドル$ for each unit sold, and you can get an additional 3ドル$ when you sell this vegetable for the first time. There are 3ドル$ units of this vegetable, all spoiled by the end of the first day.
When you sell the 2ドル$ vegetable, you can get a profit of 2ドル$ for each unit sold, and when you sell this vegetable for the first time, you can get an additional profit of 5ドル$. There are 8ドル$ units of this vegetable, of which 3ドル$ units are spoiled at the end of the first day, 3ドル$ units are spoiled at the end of the second day, and 2ドル$ units are spoiled at the end of the third day.
When only selling for 1ドル$ days, 2ドル$ units of the first vegetable and 1ドル$ units of the second vegetable should be sold.
In this case: the payoff for selling the first vegetable is 2ドル \times 3 + 3$; the payoff for selling the second vegetable is 1ドル \times 2 + 5$; and the payoff in total is $(2 \times 3 + 3) + (1 \times 2 + 5) = 16$.
When only selling for 3ドル$ days, you should sell 3ドル$ units of the first vegetable on the first day, 3ドル$ units of the second vegetable on the second day (in this case choose to sell 3ドル$ units that will spoil at the end of the second day), and sell 2ドル$ units of the second vegetable on the third day.
In this case: the payoff for selling the first vegetable is 3ドル \times 3 + 3$; the payoff for selling the second vegetable is $(3 + 2) \times 2 + 5$; and the payoff in total is $(3 \times 3 + 3) + [(3 + 2) \times 2 + 5] = 27$.