# Boxes Of Chocolates

Moderate
0/80
Average time to solve is 20m
Contributed by

## Problem statement

This is the time when Dr. Stephen wants to distribute chocolates. He has N number of boxes in a row, and each box contains some chocolates. Now, He wants to distribute chocolates to K children keeping in mind that distribution should be as fair as possible. To fairly distribute the gift boxes, he decided to give the maximum number of chocolates equally to K children.

Formally, There are N boxes with a different number of chocolates in them. The task is to divide the chocolates equally among K children where you can only choose consecutive boxes(subarray) to distribute chocolates. You need to print the maximum number of chocolates each child can get.

For Example: for the given boxes of chocolates [3,2,2,5,4,1] and 5 students.

``````Output: 2

If there is no restriction on choosing the boxes then the maximum number of chocolates the 5 students equally can have is 3 by picking all boxes except the box at index 2(0-based indexing). So total candies will be 3+2+5+4+1 = 15 and each of the 5 students will get 15/5=3 candies.

But we are allowed to choose only consecutive boxes. So if we choose boxes [0,1] then 3+2=5 then each student will have only 1 chocolate and when we choose boxes[4,6] as 5+4+1=10 then each student will have 2 chocolates. So the maximum number of chocolates each student can get is 2.
``````
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
``````The first line of input contains a single integer T, representing the number of test cases or queries to be run.

Then the T test cases follow.

The first line of each test case contains two single space-separated integers N, and K, denoting the total number of boxes and the total number of students respectively.

The second line of each test case contains 'N' single space-separated integers representing the count of chocolates in each of the N boxes.
``````
Output Format:
``````For each test case, print an integer denoting the maximum number of chocolates each child can get in a single line
``````
Constraints:
``````1 <= T <= 10
1 <= N <= 10^5
1 <= K <= 10^5
0 <= boxes[i] <= 10^5

Time Limit: 1 sec
``````
##### Sample Input 1:
``````2
5 3
1 2 3 4 5
5 4
1 2 3 4 5
``````
##### Sample Output 1:
``````5
3
``````
##### Explanation for Sample 1:
``````For the first test case, we can choose the boxes [0,4] as 1+2+3+4+5=15  each student will have 5 chocolates.

For the second test case, You can choose the boxes [2, 4] as 3+4+5=12, each student will have 3 chocolates.
``````
##### Sample Input 2:
``````1
5 8
1 2 3 4 5
``````
##### Sample Output 2:
``````0
``````
##### Explanation for Sample 2:
``````For the first test case, there is no way to choose consecutive boxes and divide chocolates from those boxes equally among 8 students
``````
Console