问题描述 :
Do you know the "Happy Farm"? It is a very popular webpage game. The player plays the role of the farmer, who can plant vegetables or grow kinds of flowers at his farm. When vegetables or flowers become ripe, the player can get in them in order to make some money. However, the greatest part of the game is to steal other farmers’ vegetables and flowers. The owner of the farm can keep a dog to help him guard against theft. Now, Farmer John intends to steal something when his neighbor David isn’t online.
Unfortunately, David keeps a dog. Can you work out a best plan for John?
Let’s suppose that David has planted n vegetables. The i-th vegetable’s value is vi. Meanwhile, stealing the i-th vegetable increases ai anger value of the dog. Due to the Internet and computer conditions, stealing the i-th vegetable will lead to an initial time delay of di. On the condition that we do not refresh the webpage, if you choose to steal the i-th vegetable in j-th turn, the actual time delay is j * di. Now, John wants to steal all of the vegetables. He can turn the dog’s anger value into zero and restart to count the number of delays by refreshing the webpage. Please pay attention that the value of the vegetable you are stealing now must be less than the value of any other vegetable that you have stolen before. It takes r units of time to refresh the webpage and the game allows you to refresh the webpage for m times at most.
During the whole theft, John wants to keep the maximum anger value of the dog at the lowest level. Meanwhile, the total time it takes cannot be longer than t units. Can you work out a plan?
输入:
The first line of input contain an integer T (T <= 10), indicating the number of test cases.
Each of the test cases must be organized in the following form. The first line of each case contain four integers n, m, r, t, (1 <= n <= 30000, 1 <= m <= 10, 1 <= r <= 100, 1 <= t <=260), with n representing the number of vegetables, m representing the maximum number for you to refresh the page, r representing the time it takes to refresh the page, and t representing the total time for John to commit his crime.
There must be three integers vi, ai, di, in each of the following n lines.The vi represents the value of each vegetable (just as there are no two same leaves in the world, so are the value of two vegetables).The ai represents the anger value of the dog. And the di represents the initial delay. 0 < vi <= 5*106, 0 < ai <= 100, n * ∑di can’t be larger than 262.
输出:
The first line of input contain an integer T (T <= 10), indicating the number of test cases.
Each of the test cases must be organized in the following form. The first line of each case contain four integers n, m, r, t, (1 <= n <= 30000, 1 <= m <= 10, 1 <= r <= 100, 1 <= t <=260), with n representing the number of vegetables, m representing the maximum number for you to refresh the page, r representing the time it takes to refresh the page, and t representing the total time for John to commit his crime.
There must be three integers vi, ai, di, in each of the following n lines.The vi represents the value of each vegetable (just as there are no two same leaves in the world, so are the value of two vegetables).The ai represents the anger value of the dog. And the di represents the initial delay. 0 < vi <= 5*106, 0 < ai <= 100, n * ∑di can’t be larger than 262.
样例输入:
3
4 1 1 10
4 2 1
3 2 3
1 2 1
2 2 1
4 0 1 13
4 2 1
3 2 3
1 2 1
2 2 1
4 0 1 14
4 2 1
3 2 3
1 2 1
2 2 1
样例输出:
6
I have no idea
8
