Farm

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 v_i. Meanwhile, stealing the i-th vegetable increases a_i 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 d_i. 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 * d_i. 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 <=2⁶⁰), 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 v_i, a_i, d_i, in each of the following n lines.The v_i 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 a_i represents the anger value of the dog. And the d_i represents the initial delay. 0 < v_i <= 5*106, 0 < a_i <= 100, n * ∑d_i can't be larger than 2⁶².

The result of the output should be printed in T lines. If there is a solution to the corresponding test case, then print out a positive integer, representing the minimum of the dog's maximum anger value during the whole theft. If John can't steal all the vegetables in the limited time, then the program should print out "I have no idea" in a single line.

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

For the first sample, John steals the first vegetable at the first time and the anger value increases to 2, costing time of 1*1. Then he refresh the webpage,
and steals the 2nd ,4th and 3rd vegetable at the second time and the anger value increases to 6, costing time of 1*3+2*1+3*1 and the time of refreshing of 1,which
adds to 10 of the total time. Considering that the anger value of the 2nd time comes to the largest, the answer is 6.For the second sample, John cannot refresh the
page at all. He must steal the 1st, 2nd, 4th, 3rd in order, and the costing time is 1*1+2*3+3*1+4*1 = 14. Because the total allowed time is 13, so it isimpossible
to steal all the vegetables.

2010 Asia Tianjin Regional Contest