Ayaan is developing a new security system for a futuristic city. The city is under threat from a series of hacking attacks that occur at specific seconds.
To defend against them, Ayaan deploys a protective firewall.
- Each time the firewall is activated at second ai, it immediately starts blocking attacks for the next k seconds.
- If another activation happens before the current protection ends, the previous firewall cycle is overridden, and the new one starts right away.
- The central server has h defense units that must be sustained. The firewall must block at least h total units of attack.
Now Ayaan needs to determine the minimum firewall duration k so that the planned activations can withstand the full attack.
Constraints
( 1 <= t <= 1000 ).
(1 <= n <= 100 ; 1 <= h <= 10^18).
( 1 <= a <= 10^9; a[i] < a[i+1] ).
Input Format
First line: integer t ( 1 <= t <= 1000 ) — number of scenarios.
For each scenario:
First line: two integers n (number of activations) and h (required defense units) (1 <= n <= 100 ; 1 <= h <= 10^18) .
Second line: n integers a1, a2, …, an ( 1 <= a <= 10^9; a[i] < a[i+1] )— the exact times when the firewall is activated (strictly increasing).
Output Format
For each test case, print the smallest integer k such that the firewall blocks at least h units.
Example 1
Input:
2
2 5
1 5
3 10
2 4 10
Output:
3
4
Explanation:
In the first scenario, if the firewall is set with k = 3, it successfully shields the server during seconds [1,2,3,5,6,7].
In the second scenario, if the firewall is set with k = 4, it keeps the defense active during seconds [2,3,4,5,6,7,10,11,12,13].
Log In to solve the Question