Bob likes to destroy buildings.
There are N buildings in a city, ith building has ai floors. Bob can do the following operation.
Choose a building, and destroy its uppermost floor with cost h. Where h is building’s height before removing the floor
You can do this operation any number of times but total cost should be less than or equal to K
Since you don’t like tall buildings you want to decrease their heights.
You have to minimise the maximum height of buildings and report this height (height of tallest among them after operations).
• Input
First line of input consists of number of test cases T . Every test case has two lines first line contains a two integers N and K , next line has N integers A1,A2,...,AN
• Output
For each test case, output a line containing answer for that test case.
• Constraints
– 1 ≤ T ≤ 103
– 1 ≤ N ≤ 105 – 1≤K≤1015 – 0≤A[i]≤106
sum of N over all test cases is less than 2 ∗ 105
• Sample Input
3
5 23
13245
5 3000000
0 1000000 2 5 99999 39
333
• Sample Output
2 999997 2