You are given an integer array and integer . In one step you can either choose some index and decrease by one (make ); or choose two indices and and set equal to (make ). What is the minimum number of steps you need to make the sum of array ? (You are allowed to make values of array negative). Input The first line contains a single integer ( ) — the number of test cases. The first line of each test case contains two integers and ( ; ) — the size of array and upper bound on its sum. The second line of each test case contains integers ( ) — the array itself. It's guaranteed that the sum of over all test cases doesn't exceed . Output For each test case, print one integer — the minimum number of steps to make . Examples , ,…, a1 a2 an k i ai = −1 ai ai i j ai aj = ai aj ≤k ∑ i=1 n ai t 1≤t≤104 n k 1≤n≤2⋅105 1≤k≤1015 a n , ,…, a1 a2 an 1≤ ≤ ai 109 n 2⋅105 ≤k ∑ i=1 n ai Input 4 1 10 20 2 69 6 9 7 8 1 2 1 3 1 2 1 10 1 1 2 3 1 2 6 1 6 8 10 Output 10 0 2 7 Note In the first test case, you should decrease
k =10 . a1 10 a times to