시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 36 7 3 27.273%

문제

대구광역시 끄트머리에 편의점 하나가 새로 개업했다. 편의점 점주를 맡은 준이는 카운터를 볼 알바를 충분히 고용하려고 한다. 그런데 하루의 각 시간대마다 필요한 알바의 수가 다르다. 이를테면 밤에는 조금 필요하고, 낮에는 많이 필요하고, 그런 식이다. 준이는 최소한의 알바를 써서 최소한의 필요한 알바의 수를 모두 충족시키고 싶다.

준이는 고민한 끝에 매 시간 필요한 알바의 수를 계산해내었다. 이 데이터는 R[0], R[1], ..., R[23]까지 주어진다. R[0]은 0시에서 1시, R[1]은 1시에서 2시, 그렇게 R[23]은 23시에서 다음날 0시 직전까지 필요한 알바의 수이다. 필요한 알바의 수는 매일 같다. 또한, 필요한 알바의 수보다 더 많은 알바가 일해도 상관없다.

준이가 알바를 모집한 결과 N명의 지원자가 알바를 하겠다고 나섰다. 각 지원자 i는 매일 특정한 시간 T[i](0 ≤ T[i] ≤ 23)시부터 정확히 8시간동안 쉬지 않고 일하겠다고 했다. 알바들은 절대 서로 도와주거나, 교대하거나, 아파서 쉬거나, 야근을 하거나, 지각하거나, 사고를 당하지 않고 무조건 제 시간에 매일 꼬박꼬박 나오고 시급을 챙겨간다.

여러분이 할 일은 R[i]와 T[i]가 모두 주어졌을 때, 필요한 최소한의 알바의 수를 구하는 프로그램을 짜는 것이다.

입력

입력의 첫째 줄에는 테스트 케이스의 갯수가 주어진다. 테스트 케이스는 20개보다 많지 않다.

각 테스트 케이스의 첫 줄에는 R[0] ~ R[23]을 나타내는 24개의 정수가 공백을 사이에 두고 주어진다. (i=0..23: 0 ≤ R[i] ≤ 1000) 그리고 둘째 줄에는 지원자의 수 N이 주어진다. (0 ≤ N ≤ 1000) 그리고 그 뒤로 N개의 줄에는 각 줄에 하나씩 T[i] (i=1..N: 0 ≤ t[i] ≤ 23) 가 주어진다.

출력

각 테스트 케이스마다 한 줄로 최소한의 필요한 알바의 수를 출력한다.

어떻게 해도 조건을 만족시키지 못하면 그 줄에 "No Solution"을 출력한다. 따옴표는 출력하지 않는다.

예제 입력

1
1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
5
0
23
22
1
10

예제 출력

1

힌트

출처

ACM-ICPC > Regionals > Asia > Iran > Tehran Site 2000 G번

  • 문제를 번역한 사람: junis3