I. [Violet] Can you save money ? (Easy version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The only difference between the easy and medium versions is the constraints on $$$n$$$.

Abushogi is in a clothing shop with $$$n$$$ items. The $$$i$$$-th item has a price of $$$a_i$$$ dinars and brings Abushogi a happiness worth of $$$b_i$$$.

The shop has given him an offer he can't refuse: if he buys exactly $$$2$$$ distinct items, he gets a $$$50\%$$$ discount (rounded down, for example if the prices is $$$7$$$ it becomes $$$3$$$) on the more expensive item. If both items have the exact same price, the discount is applied to one of them.

Abushogi has exactly $$$k$$$ dinars. He wants to buy exactly $$$2$$$ items to maximize his total happiness without exceeding his budget.

Help Abushogi find the maximum total happiness he can achieve, or tell him if it's impossible to afford any pair of items.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — denotes the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 1000$$$, $$$1 \le k \le 2 \cdot 10^9$$$) — denotes the number of items in the shop and the amount of dinars Abushogi has.

The next $$$n$$$ lines each contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^9$$$) — denotes the price and happiness value of the $$$i$$$-th item.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output

For each testcase, print a single integer — the maximum total happiness Abushogi can achieve. If it is impossible to buy exactly $$$2$$$ items without exceeding $$$k$$$ dinars, print -1.

Example
Input
3
3 10
4 5
8 6
10 6
2 5
10 100
10 100
4 12
6 4
10 5
12 10
20 20
Output
11
-1
14
Note

Abushogi can pick the 1st item ($$$a=4, b=5$$$) and the 2nd item ($$$a=8, b=6$$$). The 2nd item is more expensive, so its price becomes $$$8 / 2 = 4$$$. The total cost is $$$4 + 4 = 8$$$, which is $$$\le 10$$$. The total happiness is $$$5 + 6 = 11$$$