Josh is hungry. Starving in fact. He goes to his favorite restaurant, and to his surprise, is given the option to select all of his favorite foods from the menu. Each item on the menu has a corresponding cost and amount. Some items have the option of increasing their portion size for an additional cost. Unfortunately Josh is only allowed to have at most one of each dish, and if he opts to increase the portion size for a specific dish (if it's allowed) it may only be done once. Given Josh's budget, what is the maximum amount of food he can order?

Input

The input will begin with a line containing a single positive integer, t, representing the number of test cases to process. Each test case will begin with a line containing two space separated integers N (1 ≤ N ≤ 50) and K (1 ≤ K ≤ 10,000) which are the number of favorite dishes Josh has in this specific test case and his budget, respectively. Following will be N lines each specifying a dish. If the dish doesn't have the option to increase its portion size it will be of the form 'x y' where x is the cost for that item and y is the amount of food in that dish (1 ≤ x, y ≤ 1; 000). If the dish has an option to increase its portion size it will be of the form 'x y w h' where x and y are as before, but w is the cost to increase the size of the dish by h amount (1 ≤ w, h ≤ 1,000).

Output

For each test case print the most amount of food Josh can eat that fits within his budget. The output for each test case should be on its own line.

Example

Input:
2
3 20
5 5
10 8 5 3
15 6
2 15
10 9 3 4
5 7

Output:
16
16