요거트
면접 대비시간 제한20초메모리 제한1024 MB
요구르트 i번째 컵은 오늘부터 A_i일 뒤에 유통기한이 끝나고, 유통기한 당일과 그 이후에는 먹을 수 없다. 하루에 최대 K컵을 먹을 수 있을 때 오늘부터 먹을 수 있는 최대 개수를 구한다.
문제
요거트는 전채, 메인 요리, 디저트 어디에나 어울리는 영양식이지만, 유통기한 안에 먹어야 하고, 유통기한은 금방 다가올 수 있다. 게다가 요거트마다 유통기한이 다를 수 있다.
Lucy는 요거트를 좋아해서 요거트 N컵을 샀지만, 유통기한이 지나기 전에 다 먹지 못할까 봐 걱정하고 있다. i번째 요거트는 오늘부터 Ai일 뒤에 유통기한이 지나며, 유통기한이 지나는 날과 그 이후에는 그 요거트를 먹을 수 없다.
요거트를 아무리 좋아해도 Lucy는 하루에 요거트를 최대 K컵까지만 먹을 수 있다. 오늘부터 시작해서 Lucy가 먹을 수 있는 요거트는 최대 몇 컵인가?
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 두 정수 N과 K가 포함된 한 줄로 시작한다. 그다음 줄에는 위에서 설명한 N개의 정수 Ai가 주어진다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 Lucy가 먹을 수 있는 요거트의 최대 컵 수이다.
제한
- 1 ≤ T ≤ 100.
- 1 ≤ K ≤ N.
- 모든 i에 대해 1 ≤ Ai ≤ 109.