시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 65 14 7 24.138%

문제

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

준이는 고민한 끝에 매 시간 필요한 알바의 수를 계산해내었다. 이 데이터는 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
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

1
W3sicHJvYmxlbV9pZCI6IjczMzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzYjhcdWM3NThcdWM4MTAgXHVjNTRjXHViYzE0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzMDBcdWFkNmNcdWFkMTFcdWM1ZWRcdWMyZGMgXHViMDQ0XHVkMmI4XHViYTM4XHViOWFjXHVjNWQwJm5ic3A7XHVkM2I4XHVjNzU4XHVjODEwIFx1ZDU1OFx1YjA5OFx1YWMwMCBcdWMwYzhcdWI4NWMgXHVhYzFjXHVjNWM1XHVkNTg4XHViMmU0LiBcdWQzYjhcdWM3NThcdWM4MTAgXHVjODEwXHVjOGZjXHViOTdjIFx1YjllMVx1Yzc0MCBcdWM5MDBcdWM3NzRcdWIyOTQmbmJzcDtcdWNlNzRcdWM2YjRcdWQxMzBcdWI5N2MgXHViY2ZjIFx1YzU0Y1x1YmMxNFx1Yjk3YyBcdWNkYTlcdWJkODRcdWQ3ODggXHVhY2UwXHVjNmE5XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwIFx1ZDU1OFx1YjhlOFx1Yzc1OCBcdWFjMDEgXHVjMmRjXHVhYzA0XHViMzAwXHViOWM4XHViMmU0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM1NGNcdWJjMTRcdWM3NTggXHVjMjE4XHVhYzAwIFx1YjJlNFx1Yjk3NFx1YjJlNC4gXHVjNzc0XHViOTdjXHVkMTRjXHViYTc0Jm5ic3A7XHViYzI0XHVjNWQwXHViMjk0IFx1Yzg3MFx1YWUwOCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWFjZTAsIFx1YjBhZVx1YzVkMFx1YjI5NCBcdWI5Y2VcdWM3NzQgXHVkNTQ0XHVjNjk0XHVkNTU4XHVhY2UwLCBcdWFkZjhcdWI3ZjAgXHVjMmRkXHVjNzc0XHViMmU0LiBcdWM5MDBcdWM3NzRcdWIyOTQgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzU4IFx1YzU0Y1x1YmMxNFx1Yjk3YyBcdWMzNjhcdWMxMWMgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzU4IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM1NGNcdWJjMTRcdWM3NTggXHVjMjE4XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWNkYTlcdWM4NzFcdWMyZGNcdWQwYTRcdWFjZTAgXHVjMmY2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5MDBcdWM3NzRcdWIyOTQgXHVhY2UwXHViYmZjXHVkNTVjIFx1YjA1ZFx1YzVkMCBcdWI5ZTQgXHVjMmRjXHVhYzA0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM1NGNcdWJjMTRcdWM3NTggXHVjMjE4XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU3NFx1YjBiNFx1YzVjOFx1YjJlNC4gXHVjNzc0IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YjI5NCBSWzBdLCBSWzFdLCAuLi4sIFJbMjNdXHVhZTRjXHVjOWMwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gUlswXVx1Yzc0MCAwXHVjMmRjXHVjNWQwXHVjMTFjIDFcdWMyZGMsIFJbMV1cdWM3NDAgMVx1YzJkY1x1YzVkMFx1YzExYyAyXHVjMmRjLCBcdWFkZjhcdWI4MDdcdWFjOGMgUlsyM11cdWM3NDAgMjNcdWMyZGNcdWM1ZDBcdWMxMWMgXHViMmU0XHVjNzRjXHViMGEwIDBcdWMyZGMgXHVjOWMxXHVjODA0XHVhZTRjXHVjOWMwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM1NGNcdWJjMTRcdWM3NTggXHVjMjE4XHVjNzc0XHViMmU0LiA8dT5cdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNTRjXHViYzE0XHVjNzU4IFx1YzIxOFx1YjI5NCBcdWI5ZTRcdWM3N2MgXHVhYzE5XHViMmU0LiBcdWI2MTBcdWQ1NWMsIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM1NGNcdWJjMTRcdWM3NTggXHVjMjE4XHViY2Y0XHViMmU0IFx1YjM1NCBcdWI5Y2VcdWM3NDAgXHVjNTRjXHViYzE0XHVhYzAwIFx1Yzc3Y1x1ZDU3NFx1YjNjNCBcdWMwYzFcdWFkMDBcdWM1YzZcdWIyZTQuPFwvdT48XC9wPlxyXG5cclxuPHA+XHVjOTAwXHVjNzc0XHVhYzAwIFx1YzU0Y1x1YmMxNFx1Yjk3YyBcdWJhYThcdWM5ZDFcdWQ1NWMgXHVhY2IwXHVhY2ZjIE5cdWJhODVcdWM3NTggXHVjOWMwXHVjNmQwXHVjNzkwXHVhYzAwIFx1YzU0Y1x1YmMxNFx1Yjk3YyBcdWQ1NThcdWFjYTBcdWIyZTRcdWFjZTAgXHViMDk4XHVjMTMwXHViMmU0LiBcdWFjMDEgXHVjOWMwXHVjNmQwXHVjNzkwIGlcdWIyOTQgXHViOWU0XHVjNzdjIFx1ZDJiOVx1YzgxNVx1ZDU1YyBcdWMyZGNcdWFjMDQgVFtpXSgwICZsZTsgVFtpXSZuYnNwOyZsZTsgMjMpXHVjMmRjXHViZDgwXHVkMTMwIFx1YzgxNVx1ZDY1NVx1ZDc4OCA4XHVjMmRjXHVhYzA0XHViM2Q5XHVjNTQ4IFx1YzI2Y1x1YzljMCBcdWM1NGFcdWFjZTAgXHVjNzdjXHVkNTU4XHVhY2EwXHViMmU0XHVhY2UwIFx1ZDU4OFx1YjJlNC4gXHVjNTRjXHViYzE0XHViNGU0XHVjNzQwIFx1YzgwOFx1YjMwMCBcdWMxMWNcdWI4NWMgXHViM2M0XHVjNjQwXHVjOGZjXHVhYzcwXHViMDk4LCBcdWFkNTBcdWIzMDBcdWQ1NThcdWFjNzBcdWIwOTgsIFx1YzU0NFx1ZDMwY1x1YzExYyBcdWMyNmNcdWFjNzBcdWIwOTgsIFx1YzU3Y1x1YWRmY1x1Yzc0NCBcdWQ1NThcdWFjNzBcdWIwOTgsIFx1YzljMFx1YWMwMVx1ZDU1OFx1YWM3MFx1YjA5OCwgXHVjMGFjXHVhY2UwXHViOTdjIFx1YjJmOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWFjZTAgPHU+XHViYjM0XHVjODcwXHVhYzc0IFx1YzgxYyBcdWMyZGNcdWFjMDRcdWM1ZDAgXHViOWU0XHVjNzdjIFx1YWYyY1x1YmMxNVx1YWYyY1x1YmMxNSBcdWIwOThcdWM2MjRcdWFjZTAgXHVjMmRjXHVhZTA5XHVjNzQ0IFx1Y2M1OVx1YWNhOFx1YWMwNFx1YjJlNC48XC91PjxcL3A+XHJcblxyXG48cD5cdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NzQgXHVkNTYwIFx1Yzc3Y1x1Yzc0MCBSW2ldXHVjNjQwIFRbaV1cdWFjMDAgXHViYWE4XHViNDUwJm5ic3A7XHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWM1NGNcdWJjMTRcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjOWRjXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzJmXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCAyMFx1YWMxY1x1YmNmNFx1YjJlNCBcdWI5Y2VcdWM5YzAgXHVjNTRhXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFJbMF0gfiBSWzIzXVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgMjRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKGk9MC4uMjM6Jm5ic3A7MCZuYnNwOyZsZTsmbmJzcDtSW2ldICZsZTsgMTAwMCkmbmJzcDtcdWFkZjhcdWI5YWNcdWFjZTAgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5YzBcdWM2ZDBcdWM3OTBcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCZuYnNwOyZsZTsgTiZuYnNwOyZsZTsgMTAwMCkgXHVhZGY4XHViOWFjXHVhY2UwIFx1YWRmOCBcdWI0YTRcdWI4NWMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgVFtpXSZuYnNwOyhpPTEuLk46IDAmbmJzcDsmbGU7Jm5ic3A7dFtpXSZuYnNwOyZsZTsmbmJzcDsyMykgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNTRjXHViYzE0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjViYlx1YWM4YyBcdWQ1NzRcdWIzYzQgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YzljMCBcdWJhYmJcdWQ1NThcdWJhNzQgXHVhZGY4IFx1YzkwNFx1YzVkMCAmcXVvdDtObyBTb2x1dGlvbiZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjUzMFx1YzYzNFx1ZDQ1Y1x1YjI5NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjczMzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDYXNoaWVyIEVtcGxveW1lbnQiLCJkZXNjcmlwdGlvbiI6IjxwPkEgc3VwZXJtYXJrZXQgaW4gVGVocmFuIGlzIG9wZW4gMjQgaG91cnMgYSBkYXkgZXZlcnkgZGF5IGFuZCBuZWVkcyBhIG51bWJlciBvZiBjYXNoaWVycyB0byBmaXQgaXRzIG5lZWQuICZuYnNwO1RoZSBzdXBlcm1hcmtldCBtYW5hZ2VyIGhhcyBoaXJlZCB5b3UgdG8gaGVscCBoaW0sIHNvbHZlIGhpcyBwcm9ibGVtLiBUaGUgcHJvYmxlbSBpcyB0aGF0IHRoZSBzdXBlcm1hcmtldCBuZWVkcyBkaWZmZXJlbnQgbnVtYmVyIG9mIGNhc2hpZXJzIGF0IGRpZmZlcmVudCB0aW1lcyBvZiBlYWNoIGRheSAoZm9yIGV4YW1wbGUsIGEgZmV3IGNhc2hpZXJzIGFmdGVyIG1pZG5pZ2h0LCBhbmQgbWFueSBpbiB0aGUgYWZ0ZXJub29uKSB0byBwcm92aWRlIGdvb2Qgc2VydmljZSB0byBpdHMgY3VzdG9tZXJzLCBhbmQgaGUgd2FudHMgdG8gaGlyZSB0aGUgbGVhc3QgbnVtYmVyIG9mIGNhc2hpZXJzIGZvciB0aGlzIGpvYi48XC9wPlxyXG5cclxuPHA+VGhlIG1hbmFnZXIgaGFzIHByb3ZpZGVkIHlvdSB3aXRoIHRoZSBsZWFzdCBudW1iZXIgb2YgY2FzaGllcnMgbmVlZGVkIGZvciBldmVyeSBvbmUtaG91ciBzbG90IG9mIHRoZSBkYXkuIFRoaXMgZGF0YSBpcyBnaXZlbiBhcyBSKDApLCBSKDEpLCAuLi4sIFIoMjMpOiBSKDApIHJlcHJlc2VudHMgdGhlIGxlYXN0IG51bWJlciBvZiBjYXNoaWVycyBuZWVkZWQgZnJvbSBtaWRuaWdodCB0byAxOjAwIEEuTS4sIFIoMSkgc2hvd3MgdGhpcyBudW1iZXIgZm9yIGR1cmF0aW9uIG9mIDE6MDAgQS5NLiB0byAyOjAwIEEuTS4sIGFuZCBzbyBvbi4gTm90ZSB0aGF0IHRoZXNlIG51bWJlcnMgYXJlIHRoZSBzYW1lIGV2ZXJ5IGRheS4gVGhlcmUgYXJlIE4gcXVhbGlmaWVkIGFwcGxpY2FudHMgZm9yIHRoaXMgam9iLiBFYWNoIGFwcGxpY2FudCBpIHdvcmtzIG5vbi1zdG9wIG9uY2UgZWFjaCAyNCBob3VycyBpbiBhIHNoaWZ0IG9mIGV4YWN0bHkgOCBob3VycyBzdGFydGluZyBmcm9tIGEgc3BlY2lmaWVkIGhvdXIsIHNheSB0PHN1Yj5pPFwvc3ViPiAoMCAmbGU7IHQ8c3ViPmk8XC9zdWI+ICZsZTsgMjMpLCBleGFjdGx5IGZyb20gdGhlIHN0YXJ0IG9mIHRoZSBob3VyIG1lbnRpb25lZC4gVGhhdCBpcywgaWYgdGhlIGl0aCBhcHBsaWNhbnQgaXMgaGlyZWQsIGhlXC9zaGUgd2lsbCB3b3JrIHN0YXJ0aW5nIGZyb20gdGkgbyYjMzk7Y2xvY2sgc2hhcnAgZm9yIDggaG91cnMuIENhc2hpZXJzIGRvIG5vdCByZXBsYWNlIG9uZSBhbm90aGVyIGFuZCB3b3JrIGV4YWN0bHkgYXMgc2NoZWR1bGVkLCBhbmQgdGhlcmUgYXJlIGVub3VnaCBjYXNoIHJlZ2lzdGVycyBhbmQgY291bnRlcnMgZm9yIHRob3NlIHdobyBhcmUgaGlyZWQuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIHRvIHJlYWQgdGhlIFIoaSkgJiMzOTtzIGZvciBpPTAuLi4yMyBhbmQgdGkmIzM5O3MgZm9yIGk9MS4uTiB0aGF0IGFyZSBhbGwsIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyIG51bWJlcnMgYW5kIGNvbXB1dGUgdGhlIGxlYXN0IG51bWJlciBvZiBjYXNoaWVycyBuZWVkZWQgdG8gYmUgZW1wbG95ZWQgdG8gbWVldCB0aGUgbWVudGlvbmVkIGNvbnN0cmFpbnRzLiBOb3RlIHRoYXQgdGhlcmUgY2FuIGJlIG1vcmUgY2FzaGllcnMgdGhhbiB0aGUgbGVhc3QgbnVtYmVyIG5lZWRlZCBmb3IgYSBzcGVjaWZpYyBzbG90LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgaXMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIGZvciB0aGlzIHByb2JsZW0gKGF0IG1vc3QgMjApLiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCAyNCBpbnRlZ2VyIG51bWJlcnMgcmVwcmVzZW50aW5nIHRoZSBSKDApLCBSKDEpLCAuLi4sIFIoMjMpIGluIG9uZSBsaW5lIChSKGkpIGNhbiBiZSBhdCBtb3N0IDEwMDApLiBUaGVuIHRoZXJlIGlzIE4sIG51bWJlciBvZiBhcHBsaWNhbnRzIGluIGFub3RoZXIgbGluZSAoMCAmbGU7IE4gJmxlOyAxMDAwKSwgYWZ0ZXIgd2hpY2ggY29tZSBOIGxpbmVzIGVhY2ggY29udGFpbmluZyBvbmUgdDxzdWI+aTxcL3N1Yj4gKDAgJmxlOyB0PHN1Yj5pPFwvc3ViPiAmbGU7IDIzKS4gVGhlcmUgYXJlIG5vIGJsYW5rIGxpbmVzIGJldHdlZW4gdGVzdCBjYXNlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHRoZSBvdXRwdXQgc2hvdWxkIGJlIHdyaXR0ZW4gaW4gb25lIGxpbmUsIHdoaWNoIGlzIHRoZSBsZWFzdCBudW1iZXIgb2YgY2FzaGllcnMgbmVlZGVkLjxcL3A+XHJcblxyXG48cD5JZiB0aGVyZSBpcyBubyBzb2x1dGlvbiBmb3IgdGhlIHRlc3QgY2FzZSwgeW91IHNob3VsZCB3cml0ZSBObyBTb2x1dGlvbiBmb3IgdGhhdCBjYXNlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

  • 문제를 번역한 사람: junis3