发送快递(express)

【问题描述】

小华有 n 本不同的书（编号为$1，2，3，.....，n$），重量分别是$a_1、a_2、……、a_n$公斤（重量可以相同）。他想把这些书以快递的方式发给自己的好朋友，要求每个包裹的重量不能超过 m 公斤（可以等于 m 公斤），并且小华想把其中一些书（一组书，用书的编号给出来）放在一个包裹里，应该如何打包才能使得快递件数最少。

【输入】

输入文件名为 express.in

第一行，包含两个整数 n、m，之间用一个空格隔开，分别表示书的数量和快递包裹的最大重量。

第二行 n 个整数 ai，表示 n 本书的重量，每两个整数之间用一个空格隔开。

第三行一个整数 s，表示一共有 s 组书（每组书需要打包在一起）。如果 s=0，则无此限制。数据保证每组书的重量不超过 m。

第四行开始共 s 行，每行若干个整数，表示必须放在一个包裹里的书的编号，每两个整数之间用一个空格隔开。

【输出】

输出文件名为 express.out

输出文件一行，一个整数，即快递最少件数。

【输入输出样例 1】

express.in

5 10
8 4 8 2 5
0

express.out

3

【输入输出样例 1 说明】

第 1 本和第 4 本打包，重量是 10 公斤。第 2 本和第 5 本打包，重量是 9公斤。第 3 本单独打包，重量是 8 公斤。所以一共 3 件快递。

【输入输出样例 2】

express.in

10 80
49 11 44 18 28 24 19 10 27 29
2
1 5
4 8 2

express.out

4

【输入输出样例 2 说明】

第 1 本和第 5 本打包，第 2 本、第 4 本、第 8 本和第 10 本打包，第 3本和第 7 本打包，第 6 本和第 9 本打包。所以一共 4 件快递。

【数据范围和限制】

对于 40%的数据，$1 ≤ n ≤ 10 ^5，1 ≤ a_i ≤ 100，s=0，m$ 的值保证有解。

对于 100%的数据，1 ≤ n ≤ 10^ 5，1 ≤ a_i ≤ 100，0 ≤ s ≤ 100，m的值保证有解