Googler와 함께 춤을

여러분은 Googler(Google 직원)들이 춤을 추고, 각 무용수가 세 명의 심사위원에게 점수 세 개로 이루어진 점수 조합을 받는 쇼를 보고 있다. 각 점수 조합은 0부터 10까지의 정수 점수 세 개로 구성된다. 심사위원들의 기준은 매우 비슷하므로, 하나의 점수 조합에 2만큼 차이 나는 두 점수가 있다면 이례적이다. 어떤 점수 조합에도 2보다 더 큰 차이가 나는 점수들은 없다.

예를 들어, (8, 8, 8)와 (7, 8, 7)는 이례적이지 않다. (6, 7, 8)와 (6, 8, 8)는 이례적이다. (7, 6, 9)는 절대 나올 수 없다.

한 Googler의 총점은 그 Googler의 점수 조합에 있는 세 점수의 합이다. 한 Googler의 최고 결과는 그 Googler의 점수 조합에 있는 세 점수 중 최댓값이다. 각 Googler의 총점과 이례적인 점수 조합의 수가 주어질 때, 최고 결과가 적어도 p였을 수 있는 Googler 수의 최댓값은 얼마인가?

예를 들어, Googler가 6명 있었고 총점이 다음과 같았다고 하자: 29, 20, 8, 18, 18, 21. 이례적인 점수 조합이 2개였다는 것을 기억하고 있으며, 최고 결과가 8 이상이었을 수 있는 Googler가 몇 명인지 알고 싶다.

이 총점들과 점수 조합 중 둘이 이례적이었다는 사실을 바탕으로 하면, 점수 조합은 다음과 같았을 수 있다.

10 9 10
6 6 8 (*)
2 3 3
6 6 6
6 6 6
6 7 8 (*)

(*)로 표시된 경우가 이례적인 경우이다. 이에 따르면 적어도 하나의 점수가 8 이상인 Googler는 3명이다. 이보다 3 더 많은 Googler를 만들 수 있는 점수 조합들의 구성은 없으므로, 답은 3이다.

제한

시간 제한: 테스트 세트당 40초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 0 ≤ S ≤ N. 0 ≤ p ≤ 10. 0 ≤ $t_{i}$ ≤ 30. $t_{i}$개의 값 중 적어도 S개는 2 이상 28 이하이다.

테스트 세트 1 (공개 판정)

1 ≤ N ≤ 3.

테스트 세트 2 (비공개 판정)

1 ≤ N ≤ 100.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백 하나로 구분된 정수들이 포함된 한 줄로 구성된다. 첫 번째 정수는 Googler의 수 N이고, 두 번째 정수는 이례적인 점수 조합의 수 S이다. 세 번째 정수는 위에서 설명한 p이다. 그다음에는 Googler들의 총점인 N개의 정수 $t_{i}$가 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작하고, y는 최고 결과가 p 이상이었을 수 있는 Googler 수의 최댓값이다.