댄스 배틀

여러분의 팀이 댄스 배틀에서 실력을 증명하려고 한다. 처음에 여러분의 팀은 에너지 E점과 명예 0점을 가지고 있다. 상대해야 할 라이벌 팀이 N개 있으며, i번째 팀은 줄의 i번째에 있고 댄스 실력은 Si이다.

배틀의 각 라운드에서 줄의 다음 라이벌 팀과 마주치게 되며, 다음 행동 중 하나를 할 수 있다:

1. 댄스: 여러분의 팀은 라이벌 팀의 댄스 실력만큼 에너지를 잃고, 그 팀은 줄로 돌아오지 않는다. 명예 1점을 얻는다. 이 행동으로 에너지가 0 이하가 되면 할 수 없다.
2. 지연: 변명을 늘어놓으면("신발 끈이 안 묶였어요!") 라이벌 팀은 줄의 맨 뒤로 돌아간다. 에너지와 명예는 변하지 않는다.
3. 휴전: 라이벌 팀과 휴전을 선언하면 그 팀은 줄로 돌아오지 않는다. 에너지와 명예는 변하지 않는다.
4. 영입: 라이벌 팀을 여러분의 팀으로 영입하면 그 팀은 줄로 돌아오지 않는다. 여러분의 팀은 라이벌 팀의 댄스 실력만큼 에너지를 얻지만 명예 1점을 잃는다. 이 행동으로 명예가 0 미만이 되면 할 수 없다.

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

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 각각 두 줄로 주어진다. 첫 줄에는 두 정수 E와 N이 주어진다. 이는 여러분 팀의 에너지와 라이벌 팀의 수이다. 둘째 줄에는 N개의 정수 Si가 주어진다. i번째 값은 배틀 시작 시 줄의 i번째에 있는 라이벌 팀의 댄스 실력이다.

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

• 1 ≤ T ≤ 100.
• 1 ≤ E ≤ 106.
• 1 ≤ Si ≤ 106, 모든 i에 대해.

샘플 케이스 #1에는 라이벌 팀이 하나뿐이다. 댄스를 하면 에너지가 0이 되므로 할 수 없고, 영입을 하면 명예가 0 미만이 되므로 할 수 없다. 지연은 도움이 되지 않으므로 유일한 선택은 휴전을 선언하는 것이다. 명예 0으로 끝난다.

샘플 케이스 #2에서 한 가지 최적 전략은 다음과 같다:

1. 첫 번째 라이벌 팀에게 지연을 한다. 그 팀은 줄의 맨 뒤로 간다.
2. 두 번째 라이벌 팀에게 댄스를 한다. 에너지가 7로 줄고 명예가 1로 늘어난다.
3. 세 번째 라이벌 팀을 영입한다. 에너지가 22로 늘고 명예가 0으로 줄어든다.
4. 첫 번째 라이벌 팀(이제 다시 줄의 맨 앞에 있다)에게 댄스를 한다. 에너지가 2로 줄고 명예가 1로 늘어난다.

명예 1점으로 끝난다.