Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Hyouka

By Tamim028 · Limits 1s, 512 MB

Hotaro Oreki is a pragmatic boy who lives by "If I don't have to do something, I won't, but if I have to, I'll do it quickly."

Hotaro lives in Japan and Japan is known around the world for its cherry blossom festivals, also known as "Hanami". Many kids will join in the upcoming Hanami festival. To increase their happiness festival committee decided to gift them colorful balls to play with. But distributing balls among large number of kids and keeping them satisfied is very difficult job to do. But the good thing is that the festival committee know the number of kids coming will be some integer number K. Hotaro is given this hard task to solve on behalf of the festival committee.

There will be N boxes and each box will contain some amount of balls of same type. Hotaro needs to find the number of ball(s) for these K kids so that,

  • Each kid gets equal number of balls
  • Each kid gets only one type of balls, not balls of different types
  • Each kid gets at least one ball each for sure otherwise they will be sad
  • Amount of balls each kid gets should be maximum
  • Amount of balls that are left in the boxes should be minimum

Do you agree with Hotaro's life motto? Can you prove yourself pragmatic enough by quickly finding the number Hotaro came with?

Input

The first line of the input will contain a single integer T(1≤T≤15) that denotes the number of test cases.

For each test case, the first line will contain 2 integers N and K (1≤N,K≤100,000) where N denotes the number of boxes and K denotes the number of kids coming in Hanami festival.
Next line will contain N space-separated integers a1, a2,a3,...., aN, where, ai(1<=ai<=1000000000) denotes the the number of balls in each boxes from i'th.
Sum of all $ \sum_{i=1}^{N} a_{i} $ will always be greater than or equal to the number of kids.

Output

For each case, print the number Hotaro came with.

Sample

InputOutput
3
3 5
3 1 1
3 2
5 1 6
1 4
12
1
5
3

    Discussion

    Statistics


    65% Solution Ratio

    TheIridscntOneEarliest, 1M ago

    Anik_MBSTUFastest, 0.0s

    Tawsifiit48Lightest, 393 kB

    ash_98Shortest, 611B

    Submit

    Login to submit