C :: Cashier Machines

Time Limit: 3 Seconds    Memory Limit: 65536 KB

In new supermarkets there are cash machines to help ease manpower shortage. These machines have a large amount of coins for each available coin type. The customers should follow the following three steps to pay for their items:

  1. - At first step, customers should scan all their items to know the amount that they should pay.
  2. - Then, they can start feeding the machine by coins one by one. When the amount of money becomes enough for the item’s total price, the machine stops receiving new coins.
  3. - Finally, the machine returns the minimum number of coins for the amount that it should return back to the customer.

One of the customers wants to use this machine and he wants to minimize the number of coins in his pocket. Knowing the coins that he has in his pocket and the amount of money that he should pay, help him to spend his coins in a way that minimizes the number of coins that he would have after the payment. We know that he has enough money to buy all his items.

Input

The first line of the input contains an integer T<=100 denoting the number of test-cases. Each test-case begins with two integers N and A, denoting the number of coin types and the amount of money that the customer should pay respectively (1<=N<=20 and 1<=A<=1,000). The next N lines each contain two numbers 1<=C<=50 and 0<=K<=1,000, denoting the value of the coin type and the number of this coin type that the customer has. It is guaranteed that the coin type values are all different and one of the coin type values is equal 1.

Output

For each test-case, output on a single line the final number of coins.

Sample Input

2
3 15
1 10
4 7
2 5
3 9
1 8
2 0
9 1

Sample Output

10
4
Submit

Source: 13th Iran Nationwide Internet Contest - Shiraz