H. Video Frames
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Franky is building a massive movie projector to watch movies on the side of the Sunny. He receives $$$n$$$ video frames sorted by time. Frame $$$i$$$ arrives at time $$$T_{i}$$$ and needs $$$C_{i}$$$ cola-power to run.

He must cut the frames into continuous groups. For a group having frames $$$L, L+1, \dots, R$$$:

  • its delay is $$$T_{R} - T_{L}$$$;
  • its load is $$$\max(C_{L}, C_{L+1}, \dots, C_{R})$$$.

The total load is the sum of the loads of all groups. Sherbiny calculates the ship's engine limit and warns Franky that the total load must be $$$M$$$ or less. Find the smallest possible max delay among all groups so the movie doesn't lag.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$M$$$ ($$$1 \le n \le 10^{5}$$$, $$$1 \le M \le 10^{14}$$$) — the number of frames and the limit.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$T_{i}$$$ and $$$C_{i}$$$ ($$$1 \le T_{i} \le 10^{9}$$$, $$$1 \le C_{i} \le 10^{9}$$$) — the time and power.

It is guaranteed that $$$T_{i} \lt T_{i+1}$$$. The sum of $$$n$$$ does not exceed $$$10^{5}$$$.

Output

For each test case, output one integer — the smallest possible max delay. If it is impossible, output -1.

Example
Input
2
5 15
1 5
3 4
5 8
7 2
10 6
3 10
1 15
2 5
3 20
Output
4
-1
Note

In the first test case, one valid grouping is frames 1, 2, 3 together and frames 4,5 together. The total load is $$$8+6=14$$$, and the maximum delay is 4.

In the second test case, one frame has compute requirement larger than M, so every partition has total system load greater than M. The answer is -1.