Distribute Candies

Shaky has N (1<=N<=50000) candy boxes each of them contains a non-zero number of candies (between 1 and 1000000000). Shaky want to distibute these candies among his K (1<=K<=1000000000) IIIT-Delhi students. He want to distibute them in a way such that:

1. All students get equal number of candies.

2. All the candies which a student get must be from a single box only.

As he want to make all of them happy so he want to give as many candies as possible. Help Shaky in finding out what is the maximum number of candies which a student can get.

Input

First line contains 1<=T<=20 the number of test cases. Then T test cases follow. First line of each test case contains N and K. Next line contains N integers, ith of which is the number of candies in ith box.

Output

For each test case print the required answer in a seperate line.

Sample Input:

2
3 2 
3 1 4
4 1
3 2 3 9

Sample Output:

3
9

public class Main {
    // Binary search
    public static long requiredSum(long[] arr, int n, long k) {
        long sum = 0;
        for (long x : arr)
            sum += x;
        // Max number of candies we can give to each student
        long max = sum / k;
        // Minimum number of candies for each student = 0
        long min = 0;
        long ans = -1;
        while (max >= min) {
            // "mid" represents the the number of candies we are going
            // to give to each student(if we can)
            long mid = min + (max - min) / 2;
            long numberOfStudents = k;
            for (long x : arr) {
                // Giving "mid" amount of candies to
                // as many students as we can from the same box
                while (x - mid >= 0 && numberOfStudents > 0) {
                    x -= mid;
                    numberOfStudents--;
                }
            }
            if (numberOfStudents == 0) {
                ans = mid;
                min = mid + 1;
            } else
                max = mid - 1;
        }
        return ans;
    }
}