algo
Submit
All Submissions
Read problems statements in Russian here
Polo, the Penguin, has a lot of tests tomorrow at the university.
He knows that there are N different questions that will be on the tests. For each question i (i = 1..N), he knows C[i] - the number of tests that will contain this question, P[i] - the number of points that he will get for correctly answering this question on each of tests and T[i] - the amount of time (in minutes) that he needs to spend to learn this question.
Unfortunately, the amount of free time that Polo has is limited to W minutes. Help him to find the maximal possible total number of points he can get for all tests if he studies for no more than W minutes.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains the pair of integers N and W, separated by a space. The following N lines contain three space-separated integers C[i], P[i] and T[i] (i = 1..N).
Output
For each test case, output a single line containing the answer to the corresponding test case.
Constraints
1 ≤ T ≤ 100
1 ≤ N ≤ 100
1 ≤ C[i], P[i], T[i] ≤ 100
1 ≤ W ≤ 100
Example
Input:
1
3 7
1 2 3
2 3 5
3 3 3
Output:
11
Explanation
Example case 1. The best choice is to learn the first and the third questions and get 1*2 + 3*3 = 11 points.