当前没有测试数据。

Background

小华有 n 本不同的书（编号为 1，2，3，.....，n），重量分别是 a$_1$、a$_2$、……、a$_n$公斤（重量可以相同）。

他想把这些书以快递的方式发给自己的好朋友，要求每个包裹的重量不能超过 m 公斤（可以等于 m 公斤），

并且小华想把其中一些书（一组书，用书的编号给出来）放在一个包裹里，应该如何打包才能使得快递件数最少。

Format

Input

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

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

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

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

Output

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

Samples

5 10
8 4 8 2 5
0

3

Limitation

对于 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 的值保证有解。