问题描述

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

输入格式

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

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

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

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

输出格式

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

样例

5 10
8 4 8 2 5
0

3

样例解释

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

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

4

样例解释

第 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$的值保证有解

来源

2021 NOIP 山东(小学组)