All Zeros :
Difficulty Level : Medium
Submissions : 880
Asked In :
Marks :15
: 8 | : 0
You are given an integer array $$$A$$$ containing $$$n$$$ integers. You are also given an integer $$$m$$$.
For a fixed value $$$k$$$, you can perform the following operation on the array $$$A$$$ as many times as you want :
- Choose an index $$$i$$$ $$$(1 \le i \le n)$$$ and assign $$$A[i] := max(0,A[i]-k)$$$.
Your task is to find the smallest value of $$$k$$$ such that you can make all the elements of array $$$A$$$ equal to $$$0$$$ in atmost $$$m$$$ operations. If there is no such possible value of $$$k$$$, print $$$-1$$$.
The first line of input contains an integer $$$t \hspace{2pt} (1 \le t \le 10^4)$$$ — the number of testcases. The description of $$$t$$$ testcases follows.
The first line of each testcase contains two space separated integers $$$n$$$ $$$(1 \le n \le 10^5)$$$ and $$$m$$$ $$$(0 \le m \le 10^{18})$$$ — the number of elements in the arrays $$$A$$$ and the maximum number of operations you can perform.
The second line of each testcase contains $$$n$$$ space separated integers $$$a_0, a_1, ... a_n$$$ $$$(0 \le a_i \le 10^{13})$$$ — the elements of array $$$A$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$10^5.$$$
For each test case, print the minimum value of $$$k$$$ such that you can make all the elements of array $$$A$$$ equal to $$$0$$$ in atmost $$$m$$$ operations or $$$-1$$$ in a single line.
34 63 5 1 43 21 0 13 11 0 1
3 1 -1
