MAIN8_C - Shake Shake Shaky

no tags 

 

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

Shaky has N (1<=N<=50000) candy boxes each of them contains a non-zero number of candies (between 1 and 1000000000). Shakey 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.

Example

Input:
2
3 2 
3 1 4
4 1
3 2 3 9

Output:
3
9

hide comments
anubhawiiitu: 2018-01-02 15:52:46

TLE with int
Accepted with long int

themast3r: 2017-11-04 23:49:02

AC in 2nd go due to stupid problem description. Make sure to:-
1. Print 0 if not possible, this costed me WA.
2. More than one(two, three, four, .....) persons can get candies from the same box.

Last edit: 2017-11-04 23:50:59
jatin03: 2017-08-17 19:04:40

Getting constant tle cant understand

tushar091: 2017-07-05 19:07:16

will the long suffice or do i use long long unsigned

Last edit: 2017-07-05 21:14:50
praney_rai: 2017-06-14 10:26:46

done using binary search

anurag44: 2017-05-23 11:41:53

Consider the case when the no of candidates is more than the sum of all candies

aeon: 2017-04-10 05:48:58

consider the case:
1 1
1
gives me 1 WA
#simple BS

ahmadmeaaa: 2017-03-31 14:09:26

nice one really useful

king_algo: 2017-02-05 11:32:46

Yaaayyy !!!!! my 15th !!! AC in one go.

vengatesh15: 2016-12-29 05:51:41

done using binary search...


Added by:Mahesh Chandra Sharma
Date:2011-04-20
Time limit:0.622s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for NSIT-IIITA Main contest #8