E. 硬币购物

时间限制：1000 ms

内存限制：256 MB

题目描述 有 n种硬币，面额用数组 ai 表示。

回答 q 次询问：在第 i 种硬币至多使用 bi 枚的情况下，要组成c 的总金额，有多少种方案。

输入格式 第一行包含一个整数n 。

第二行包含 n个正整数 ai。

第三行包含一个整数 q。

接下来 q 行，每行包含 n+1 个整数，分别是数组 bi 与 c。

输出格式 对于每次询问输出一行，一个整数，表示构成金额 的方案数。

样例

样例输入

2

1 2

2

5 4 10

1000 2 900

样例输出

2

3

对于所有测试点，保证 1 < ai,bi,c<1e5,1 < n <= 4。,1 < q <= 2000