1556. [POJ1275]出纳员的雇佣

【题目描述】

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

经理已经提供你一天的每一小时需要出纳员的最少数量——$r_0,r_1,\cdots, r_{23}$。$r_0$表示从午夜到上午1：00需要出纳员的最少数目，$r_1$表示上午1：00到2：00之间需要的，等等。每一天，这些数据都是相同的。有$n$人申请这项工作，每个申请者$i$在每24小时中，从一个特定的时刻开始连续工作恰好8小时，定义$t_i(0\leq t_i\leq 23)$为上面提到的开始时刻。也就是说，如果第$i$个申请者被录取，他（她）将从$t_i$时刻开始连续工作8小时。

你将编写一个程序，输入$r_i(0\leq i\leq 23,r_i\leq 1000)$和$t_i(1\leq i\leq n, 0\leq t_i\leq 23)$，它们都是非负整数，计算为满足上述限制需要雇佣的最少出纳员数目。在每一时刻可以有比对应的$r_i$更多的出纳员在工作。

【输入格式】

输入文件的第一行为测试点个数$T(T\leq 20)$。

每组测试数据的第一行为24个整数表示$r_0,r_1,\cdots, r_{23}$。

接下来一行是$n$，表示申请者数目，接下来每行包含一个整数$t_i$。

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

【输出格式】

对于每个测试点，输出只有一行，包含一个整数，表示需要出纳员的最少数目。

如果无解，你应当输出“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比赛：Tehran Regionals 2000, Cashier Employment

POJ 1275 Cashier Employment