아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

예선 라운드 (Small)

시간 제한5초메모리 제한512 MB

요약
P개 문제 각각을 푼 사람 수가 주어질 때, 서로 다른 C개 이상의 문제를 푼 사람 수의 최댓값을 구한다.
난이도

보통10점 중 6점

유형
그리디, 정렬, 조합론
정답자
아직 제출이 없습니다

문제

어떤 프로그래밍 대회의 예선을 통과했다. 나와 함께 통과한 참가자가 몇 명인지 알고 싶은데, 손에 있는 정보는 문제별 정답자 수뿐이다.

예선에는 문제가 PP개 나왔고, ii번 문제를 완전히 푼 참가자는 SiS_i명이다. 본선에 진출하려면 문제를 CC개 이상 풀어야 한다. 이 정보만으로 본선에 진출한 참가자 수의 최댓값을 구한다.

한 참가자가 같은 문제를 두 번 푸는 일은 없으므로, 문제를 CC개 풀었다는 말은 서로 다른 문제 CC개를 풀었다는 뜻이다.

입력

첫째 줄에 테스트 케이스의 수 TT가 주어진다. 이어지는 TT개의 줄에 테스트 케이스가 하나씩 주어진다. 각 줄에는 공백으로 구분된 정수가 놓인다. 먼저 PP와 CC가 오고, 그 뒤에 정수 PP개 S0,S1,…,SP−1S_0, S_1, \dots, S_{P-1}이 온다.

제한

  • 1≤T≤1001 \le T \le 100
  • 1≤P≤61 \le P \le 6
  • 1≤C≤P1 \le C \le P
  • 0≤Si≤10000 \le S_i \le 1000

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. xx는 1부터 시작하는 테스트 케이스 번호이고, yy는 문제를 CC개 이상 푼 참가자 수의 최댓값이다.

예제1

  1. 예제 1

    입력
    2
    2 2 73 100
    3 2 245 272 238
    
    예상 출력
    Case #1: 73
    Case #2: 377