HALCAND - Halum and Candies

no tags 

Halum has been elected as the captain of his school's football team. To celebrate this, he is going to throw a party. Halum bought candies of N different flavors for the party. There are ai number of candies of the ith flavor where (1 ≤ i ≤ N). To satisfy a guest he has to give him/her some positive number of candies of at least K different flavors. Otherwise the guest is not satisfied. Given this information now you have to find the maximum number of guests Halum can satisfy with the available candies.

Input

First line of the input contains an integer T (1 ≤ T ≤ 200), denoting the number of test cases. T cases follow.
First line of each case contains two integers N and K (1 ≤ K ≤ N ≤ 1000). N space separated integers a1, a2… aN follow in the next line (0 ≤ ai ≤ 10^9). The ith of these integers ai denotes the number of candies of ith flavor (1 ≤ i ≤ N).

Output

For each case print one line containing "Case X: Y" (without the quotes) where X is the case number starting from 1 and Y is an integer denoting the maximum number of guests who can be satisfied.

Example

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

Output:
Case 1: 1
Case 2: 6
Case 3: 4

hide comments
akjol2049: 2018-11-29 12:56:03

can you give any corner cases pls..dont know why i am getting WA

ssunitk: 2017-05-23 08:53:50

@imranzaid could u please check my solution id no 19458372 . i couldnt understand where i m going wrong , my code is working fine for all the test cases available .

Rully Soelaiman: 2017-04-26 13:11:27

Need Binary Search Methods


Added by:imranziad
Date:2017-04-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:NHSPC National 2017