댄스 배틀

여러분의 팀은 이제 댄스 배틀에서 실력을 증명하려 한다! 처음에 여러분의 팀은 E점의 에너지를 가지고 있으며, 명예 점수는 없다. 상대해야 하는 라이벌 팀이 N개 있다. 이 팀들 중 i번째 팀은 대기열의 i번째에 있으며, 춤 실력은 $S_{i}$이다.

배틀의 각 라운드에서는 대기열의 다음 라이벌 팀을 상대하며, 다음 행동 중 하나를 선택할 수 있다.

• 춤추기: 여러분의 팀은 라이벌 팀의 춤 실력과 같은 양의 에너지를 잃고, 그 팀은 대기열로 돌아오지 않는다. 명예 한 점을 얻는다. 이 행동으로 에너지가 0 이하로 떨어진다면 이 행동을 할 수 없다.

• 지연하기: 핑계를 대고("우리 신발 끈이 묶여 있지 않아!") 라이벌 팀을 대기열의 맨 뒤로 돌려보낸다. 에너지와 명예는 변하지 않는다.

• 휴전하기: 라이벌 팀과의 휴전을 선언하고, 그 팀은 대기열로 돌아오지 않는다. 에너지와 명예는 변하지 않는다.

• 영입하기: 라이벌 팀을 여러분의 팀으로 영입하고, 그 팀은 대기열로 돌아오지 않는다. 여러분의 팀은 라이벌 팀의 춤 실력과 같은 양의 에너지를 얻지만, 명예 한 점을 잃는다. 이 행동으로 명예가 0 미만으로 떨어진다면 이 행동을 할 수 없다.

대기열에 라이벌 팀이 더 이상 없으면 배틀이 끝난다. 최적의 결정을 내릴 때, 배틀이 끝난 후 가질 수 있는 명예의 최댓값은 얼마인가?

제한

1 ≤ T ≤ 100. 테스트 세트당 제한 시간: 20초. 메모리 제한: 1GB. 1 ≤ E ≤ $10^{6}$. 모든 i에 대해, 1 ≤ $S_{i}$ ≤ $10^{6}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 5.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 1000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 줄로 이루어진다. 첫 번째 줄에는 여러분의 팀의 에너지와 라이벌 팀의 수를 나타내는 두 정수 E와 N이 주어진다. 두 번째 줄에는 N개의 정수 $S_{i}$가 주어지며, 이 중 i번째 정수는 배틀이 시작될 때 대기열의 i번째에 있는 라이벌 팀의 춤 실력을 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 배틀이 끝난 후 가질 수 있는 명예의 최댓값이다.

예제 케이스 #1에서는 라이벌 팀이 하나뿐이다. 춤을 추면 에너지가 0까지 떨어지므로 그들과 춤출 수 없고, 영입하면 명예가 0 미만으로 떨어지므로 그들을 영입할 수도 없다. 지연하기는 도움이 되지 않으므로, 유일한 선택지는 휴전을 선언하는 것이다. 명예 0점으로 끝낸다.

예제 케이스 #2에서 최적의 전략 중 하나는 다음과 같다.

• 첫 번째 라이벌 팀을 상대로 지연한다. 그 팀은 대기열의 맨 뒤로 이동한다.

• 두 번째 라이벌 팀을 상대로 춤춘다. 에너지는 7까지 떨어지고, 명예는 1까지 증가한다.

• 세 번째 라이벌 팀을 영입한다. 에너지는 22까지 증가하고, 명예는 0까지 감소한다.

• 첫 번째 라이벌 팀을 상대로 춤춘다(이 팀은 이제 다시 대기열의 맨 앞에 있다). 에너지는 2까지 떨어지고, 명예는 1까지 증가한다.

명예 1점으로 끝낸다.