Chef likes shopping, and especially he likes to buy oranges. But right now he is short of money. He has only k rubles. There are n oranges. The i-th one costs costi rubles and has weight equal to weighti. Chef wants to buy a set of oranges with the maximal possible weight. Please help him, and tell him this weight.

Input
The first line of the input contains an integer T  denoting the number of test cases. The first line of each test case contains two numbers n and k. The following n lines contain two numbers costi and weighti respectively. 

Output
For each test case, output a single line containing maximal weight among all the affordable sets of oranges. 

Constraints

1 ≤ T ≤  250 
1 ≤ n ≤  10 
1 ≤ k ≤  100000000 
1 ≤ weighti ≤  100000000 
1 ≤ costi ≤  100000000 


Example
Input:
2
1 3
2 2
3 4
2 1
2 2
3 5

Output:
2
5
 

Scoring
Subtask 1 (30 points): All the oranges' weights equals to 1.
Subtask 2 (30 points):   N = 5  
Subtask 2 (40 points):  See the constraints
test = input()
from itertools import combinations
while test:
    test-=1
    n,k = map(int,raw_input().split())
    weights = []
    costs = []
    index = []
    for i in range(n):
        c,w = map(int,raw_input().split())
        costs.append(c)
        weights.append(w)
        index.append(i)
    max = 0
    for r in range(1,n+1):
        for sub in combinations(index,r):
            cost = 0
            weight = 0
            for i in sub:
                cost += costs[i]
                weight += weights[i]
            if cost <=k and weight > max:
                max = weight
    print max