Yogurt
면접 대비시간 제한20초메모리 제한1024 MB
N개의 요거트 컵의 유통기한 Ai와 하루 최대 섭취량 K가 주어질 때, 오늘부터 먹을 수 있는 요거트의 최대 개수를 구한다.
문제
Yogurt can be a nutritious part of an appetizer, main course, or dessert, but it must be consumed before it expires, and it might expire quickly! Moreover, different cups of yogurt might expire on different days.
Lucy loves yogurt, and she has just bought N cups of yogurt, but she is worried that she might not be able to consume all of them before they expire. The i-th cup of yogurt will expire Ai days from today, and a cup of yogurt cannot be consumed on the day it expires, or on any day after that.
As much as Lucy loves yogurt, she can still only consume at most K cups of yogurt each day. What is the largest number of cups of yogurt that she can consume, starting from today?
입력
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with one line containing two integers N and K, as described above. Then, there is one more line with N integers Ai, as described above.
출력
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of cups of yogurt that Lucy can consume, as described above.
제한
- 1 ≤ T ≤ 100.
- 1 ≤ K ≤ N.
- 1 ≤ Ai ≤ 109, for all i.