반올림 오차

어떤 프로그래밍 언어가 최고인지에 관한 해묵은 논쟁을 마침내 끝내기 위해, 총 N명에게 가장 좋아하는 언어를 물어보고 있다. 이는 자유 응답식 질문이다. 각 사람은 어떤 언어든 자유롭게 답할 수 있으며, 세상에는 무한히 많은 언어가 있다.

몇몇 사람은 이미 응답했으며, 당신은 이 정보를 인원수의 목록으로 모았다. 예를 들어 1 2은 지금까지 3명에게 물었고, 한 명은 특정 언어를 선택했으며 다른 두 명은 그와 다른 어떤 언어를 선택했다는 뜻이다.

당신은 각 언어와 그 언어를 선택한 사람의 비율을 백분율로 나열한 표를 통해 결과를 발표할 계획이다. 각 백분율은 가장 가까운 정수로 반올림하며, 소수 부분이 0.5 이상인 백분율은 올림한다. 따라서 예를 들어 12.5%는 13%로 올림되고, 99.5%는 100%로 올림되며, 12.4999%는 12%로 내림된다.

이와 같은 설문 조사에서는 반올림된 백분율의 합이 정확히 100이 되지 않을 때도 있다. 남은 사람들에 대한 설문을 마친 뒤, 반올림된 백분율의 합으로 가능한 최댓값은 얼마인가?

제한

1 ≤ T ≤ 100. 1 ≤ L < N. 모든 i에 대해 1 ≤ $C_{i}$. 모든 $C_{i}$ 값의 합 < N. 테스트 세트당 시간 제한: 10초. 메모리 제한: 1GB.

테스트 세트 1 (공개)

2 ≤ N ≤ 25.

테스트 세트 2 (공개)

2 ≤ N ≤ 250.

테스트 세트 3 (비공개)

2 ≤ N ≤ $10^{5}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 각각 두 줄로 이루어진 T개의 테스트 케이스가 주어진다. 첫 번째 줄에는 두 정수 N과 L이 주어진다. N은 설문 조사 대상자의 총인원이고, L은 이미 응답한 사람들의 답변에 등장한 서로 다른 언어의 총개수이다. 두 번째 줄에는 L개의 정수 $C_{i}$가 주어진다. 이 중 i번째 정수는 등장한 언어 중 i번째 언어를 가장 좋아한다고 답한 사람의 수이다.

각 테스트 케이스마다 Case #x: y을 담은 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y은 위에서 설명한 백분율 합으로 가능한 최댓값이다.

예제 케이스 #1에서는 두 명이 이미 응답했으며 서로 다른 언어를 선택했다. 한 명은 아직 응답하지 않았다. 그 사람이 세 번째 언어를 선택하면 반올림된 백분율의 합은 33 + 33 + 33 = 99가 된다. 그러나 그 사람이 이미 선택된 언어 중 하나를 선택하면 반올림된 백분율의 합은 67 + 33 = 100이 된다. 따라서 100이 가능한 합의 최댓값이다.

예제 케이스 #2에서는 다른 네 명이 무엇을 선택하든, 각 언어의 백분율은 언제나 반올림할 필요가 없는 10의 정확한 배수이며, 그 합은 정확히 100가 된다.

예제 케이스 #3에서 최적의 경우 중 하나는 다음과 같다. 남은 두 사람이 각각 아직 선택되지 않은 언어를 선택하면, 반올림된 백분율의 합은 50 + 17 + 17 + 17 = 101이 된다.

예제 케이스 #4에서는 남은 한 사람이 이미 선택된 언어를 선택하는지와 관계없이 반올림된 백분율의 합이 99이 된다.