16445 | 요거트

요거트는 전채 요리, 주 요리 또는 후식에서 영양가 있는 일부가 될 수 있지만, 유통기한이 지나기 전에 먹어야 하며 유통기한이 빨리 다가올 수도 있다! 게다가 요거트 컵마다 유통기한이 서로 다른 날일 수 있다.

Lucy는 요거트를 아주 좋아해서 방금 요거트 N컵을 샀지만, 유통기한이 지나기 전에 모두 먹지 못할까 봐 걱정한다. i번째 요거트 컵의 유통기한은 오늘로부터 $A_{i}$ 일 뒤이며, 유통기한 당일이나 그 이후에는 먹을 수 없다.

Lucy가 요거트를 아무리 좋아해도 하루에 먹을 수 있는 요거트는 최대 K컵뿐이다. 오늘부터 먹기 시작할 때, 그녀가 먹을 수 있는 요거트 컵의 최대 개수는 얼마인가?

1 ≤ T ≤ 100. 테스트 세트당 시간 제한: 20초. 메모리 제한: 1 GB. 1 ≤ K ≤ N. 모든 i에 대해 1 ≤ $A_{i}$ ≤ $10^{9}$ .

1 ≤ N ≤ 1000. K = 1.

1 ≤ N ≤ 5000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 두 정수 N과 K가 포함된 한 줄로 시작한다. 그다음 위에서 설명한 N개의 정수 $A_{i}$ 가 포함된 한 줄이 더 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y은 위에서 설명한 Lucy가 먹을 수 있는 요거트 컵의 최대 개수이다.

Case #1: 1
Case #2: 3

2
2 2
1 1
6 2
1 1 1 7 7 7

Case #1: 2
Case #2: 5

예제 케이스 #1에서 요거트 두 컵은 각각 하루 뒤에 유통기한이 만료된다. 오늘 Lucy는 그중 하나를 먹을 수 있지만, 하루에 최대 한 컵만 먹을 수 있으므로 둘 다 먹을 수는 없다. 내일은 남은 요거트 컵의 유통기한이 이미 지났으므로 먹을 수 없다.

예제 케이스 #1에서 Lucy는 하루에 최대 두 컵을 먹을 수 있으므로 요거트를 모두 먹을 수 있다.