Description
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 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 th vegetable sold, you can get income.
In particular, since the policy encourages merchants to conduct diversified sales, when selling the th vegetable for the first time, they will also get an additional income of .
At the start of the operation, the stock of vegetable is 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 th vegetable, there is a freshness value , and there will be 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 satisfying the condition , units of vegetables will spoil at the end of day.
In particular, if , then units of vegetables will spoil by the end of days.
Note that when , 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 units at most.
Now, Little N has query. Each query is of the form: Given , if you need to sell for days, what is the maximum profit you can get?
Input Format
The first line contains three positive integers , 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 lines, enter four non-negative integers in each line to describe the characteristics of a vegetable, which are in turn, and the meanings are as described above.
In the next lines, enter a non-negative integer in each line, the meaning is as described above.
Output Format
Output lines, each line contains an integer, and the number in line represents the answer to question .
Sample Input
2 3 2
3 3 3 3
2 5 8 3
1
3
Sample Output
16
27
Explanation for Sample Output
There are two types of vegetables:
When selling the vegetable, you can get for each unit sold, and you can get an additional when you sell this vegetable for the first time. There are units of this vegetable, all spoiled by the end of the first day.
When you sell the vegetable, you can get a profit of for each unit sold, and when you sell this vegetable for the first time, you can get an additional profit of . There are units of this vegetable, of which units are spoiled at the end of the first day, units are spoiled at the end of the second day, and units are spoiled at the end of the third day.
When only selling for days, units of the first vegetable and units of the second vegetable should be sold.
In this case: the payoff for selling the first vegetable is ; the payoff for selling the second vegetable is ; and the payoff in total is .
When only selling for days, you should sell units of the first vegetable on the first day, units of the second vegetable on the second day (in this case choose to sell units that will spoil at the end of the second day), and sell units of the second vegetable on the third day.
In this case: the payoff for selling the first vegetable is ; the payoff for selling the second vegetable is ; and the payoff in total is .
Constraints
Test case | Property | Property | |||
---|---|---|---|---|---|
No | No | ||||
No | No | ||||
No | No | ||||
No | No | ||||
No | No | ||||
No | No | ||||
No | No | ||||
No | No | ||||
No | No | ||||
No | No | ||||
No | No | ||||
Yes | No | ||||
No | Yes | ||||
No | No | ||||
No | No | ||||
Yes | Yes | ||||
Yes | No | ||||
No | Yes | ||||
No | No | ||||
No | No | ||||
Yes | Yes | ||||
Yes | No | ||||
No | Yes | ||||
No | No | ||||
No | No |
Property : all are ;
Property : All are .
For all test data, it is guaranteed that in sets of queries are different from each other.
For all test data, it is guaranteed that , .
Comments