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$$$:
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.
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}$$$.
For each test case, output one integer — the smallest possible max delay. If it is impossible, output -1.
25 151 53 45 87 210 63 101 152 53 20
4-1
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.
