题目描述

小明的口袋里有四种面值的硬币，面值分别为 $c_1, c_2, c_3, c_4$。他去超市购物，每次购物时携带的硬币数量有限：第 $i$ 种硬币最多带 $d_i$ 枚。请问每次购买价值为 $s$ 的商品时，有多少种不同的付款组合方式。

输入格式

第一行五个整数 $c_1, c_2, c_3, c_4, n$，分别表示四种硬币的面值和购物的次数。

接下来 $n$ 行，每行五个整数 $d_1, d_2, d_3, d_4, s$，描述一次购物场景：每种硬币的携带数量上限以及需要付款的金额。

输出格式

对于每次购物，输出一行一个整数，表示满足条件的付款方案数。

样例

1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

4
27

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq c_i, d_i, s \leq 10^5$，$1 \leq n \leq 1000$。

思路提示

先用完全背包预处理无限制时凑出每个面值的方案数，再用容斥原理减去不满足硬币数量限制的方案。