Question

Jay works for support project where he has to resolve some tickets each day (denoted by A[i]). He knows, ahead of time, the number of tickets for each day for N days. Let A be an array of length N. Each element A[i] (where i=1 to i=N) denotes number of tickets to resolve on ith day. Jay is struggling to balance his work life. On some days, workload is huge and on other days, it is very little. Now he can procrastinate and choose to postpone up to K tickets to next day. However, tickets can only be postponed once. (Refer example 2 for more clarity). Find optimal solution where workload can be distributed as evenly as possible with above constraints and print the maximum number of tickets he needs to resolve on given days. Constraints 1<= T <= 50 1<= N <= 100 1<= K <= 100 1<= A[i] <= 10^9 Input Format First line is integer T denoting number of test cases. For each test case: First line is N K described above Next line is N spaced integers denoting number of tickets for each day Output For each test case, print a single integer per line denoting maximum number of tickets Jay needs to resolve after optimal rearrangement with above constraints. Example Input 2 3 100 3 1 2 3 1532 28 31 37 Output 2 37 Explanation Initially highest workload is on first day (3 tickets). Now 1 ticket should be postponed from day 1 to day 2. So array is [2,2,2] and maximum workload is 2. For second testcase, no rearrangement is required, hence the output is 37. Example Input 1 3 100 7 1 1 Output: 4 Explanation: Initially highest workload is on first day (7 tickets). Now we postpone 4 tickets from day 1 to day 2. Array now looks like [3,5,1]. Now on day 2, even K is 100, we can only postpone 1 ticket since tickets can only be postponed once. (In other words, 4 tickets out 5 which were postponed from day 1 has to be resolved on day 2. They cannot be postponed any further). So after postponing 1 ticket array looks like [3,4,2] and maximum workload is 4, hence answer is 4.

Answer 1

Answer:

WHAT IS THIS ............

Explanation: