Problem1088--「一本通 3.4 例 2」出纳员问题

1088: 「一本通 3.4 例 2」出纳员问题

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

原题来自:Asia 2000,题面可参考 ZOJ 1420

Tehran 的一家每天 242424 小时营业的超市,需要一批出纳员来满足它的需要。超市经理雇佣你来帮他解决问题——超市在每天的不同时段需要不同数目的出纳员(例如,午夜时只需要一小批,而下午则需要很多)为顾客提供优质服务。他希望雇佣最少数目的出纳员。

经理已经提供给你一天的每一小时需要出纳员的最少数量——R(0),R(1),⋯ ,R(23)R(0),R(1),\cdots ,R(23)R(0),R(1),,R(23)R(0)R(0)R(0) 表示从午夜到上午 1:00 需要出纳员的最小数目,R(1)R(1)R(1) 表示上午 1:00 到 2:00 需要的,等等。每一天,这些数据都是相同的。有 NNN 人申请这项工作,每个申请者 iii 在每 242424 小时中,从一个特定的时刻开始连续工作恰好 888 小时,定义 tit_iti 为上面提到的开始时刻。也就是说,如果第 iii 个申请者被录取,他(她)将从 tit_iti 时刻开始连续工作 888 小时。

请你编写一个程序,输入 R(i)R(i)R(i)tit_iti,它们都是非负整数,计算为满足上述限制需要雇佣的最少出纳员数目。在每一时刻可以有比对应的 R(i)R(i)R(i) 更多的出纳员在工作。


Input

第一行为测试点的数目 TTT

对于每组测试数据,第一行为 242424 个整数,表示 R(0),R(1),R(2),⋯ ,R(23)R(0),R(1),R(2),\cdots ,R(23)R(0),R(1),R(2),,R(23)
接下来一行一个正整数 NNN,表示申请者数目;
接下来 NNN 行每行一个整数 tit_iti

两组测试数据之间没有空行。


Output

对于每个测试点,输出一行,包含一个整数,表示需要出纳员的最小数目。如果无解,输出No Solution。


Sample Input

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

Sample Output

1

HINT

对于全部数据,1≤T≤20,0≤N≤1000,0≤R(i)≤1000,0≤ti≤231\le T\le 20,0\le N\le 1000,0\le R(i)\le 1000,0\le t_i\le 231T20,0N1000,0R(i)1000,0ti23


Source/Category


Submit Status