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.
def knapsack(weights,values,maxw):
    n=len(weights)
    m=[]
    tmp=[]
    for i in xrange(0,maxw+1):
	tmp.append(0)
    m.append(tmp)
    for i in xrange(1,n):
	tmp=[]
	for j in xrange(0,maxw+1):
	    if j<weights[i]:
		tmp.append(m[i-1][j])
	    else:
		tmp.append(max(m[i-1][j],m[i-1][j-weights[i]]+p[i]))
	m.append(tmp)
    return m[n-1][maxw]
    
t=int(raw_input())
while t:
    nw=map(int,raw_input().split())
    n=nw[0]
    w=nw[1]
    p=[-1]
    tt=[-1]
    for i in xrange(0,n):
	tr=map(int,raw_input().split())
	p.append(tr[1]*tr[0])
	tt.append(tr[2])
    print knapsack(tt,p,w)
    t-=1