SPOJ.com - Problem MAIN8

MAIN8_C - Shake Shake Shaky

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

Submit solution!

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

hide comments

2012-02-10 15:33:44 arshan qureshi
i don't know if my algo is wrong , can you provide us with some more test cases ,plz ...or anyone having the correct answer.

2011-11-15 06:01:26 Mahesh Chandra Sharma
@Lokesh kumar -> Yes

2011-10-09 12:51:03 sri
5 4
2 4 1 3 1
what is the answer?
2 or 1????

2011-10-04 22:58:14 LOKESH KUMAR
can two persons can get candies from same box.for eg: if a box has 4 candies then can 2 persons get 2 candies each from same box????

2011-09-08 18:36:39 blashyrkh
@Zachary Ziebarth: Random subset of test cases (anti-cheating)? And failure on some test cases?

Last edit: 2011-09-08 18:37:14

2011-09-08 13:47:26 Zachary Ziebarth
Something is bugged with this problem. Check my submission history, I didn't make a single change between my last incorrect submission, and my accepted submission, and pretty much all of my changes before then were trivial (not affecting the algorithm or output). The only difference was that my correct submission was made about 13 hours later.

2011-07-30 03:03:38 neerajcrespo
getting WA. I sorted in dec. order then printed kth index if k<=n.. m I wrong?

2011-06-25 17:02:59 mukesh tiwari
Increase the time limit. I am getting TLE for Haskell code.

2011-06-25 12:33:41 mukesh tiwari
after this , try https://www.spoj.pl/problems/PIE/

2011-06-09 20:57:28 Gurpreet Singh
This test case might be helpful :

5 4
2 4 1 3 1