[HAOI2008]硬币购物

一共有 $4$ 种硬币，面值分别为 $c_1, c_2, c_3, c_4$。

某人去商店买东西，一共去了 $tot$ 次。第 $i$ 次他带了第 $j$ 种硬币各 $d_j$ 枚（$j=1,2,3,4$），要买价值为 $s$ 的东西。

请问每次购物有多少种付款方法。两种付款方法不同，当且仅当至少有一种硬币的使用枚数不同。

输入格式

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

接下来 $tot$ 行，每行包含五个非负整数 $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

样例解释

四种硬币的面值为 $1, 2, 5, 10$，共购物两次。

第一次带 $1$ 元硬币 $3$ 枚、$2$ 元硬币 $2$ 枚、$5$ 元硬币 $3$ 枚、$10$ 元硬币 $1$ 枚，要凑出 $10$ 元，共有 $4$ 种方法。

数据范围

对于所有测试数据：

• $1\le tot\le 1000$；
• $1\le c_j\le 10^5$；
• $0\le d_j\le 10^5$；
• $0\le s\le 10^5$。

来源与许可

本题为 HAOI 2008 试题「硬币购物」，题面与测试数据整理自 BZOJ 1042。

样例 1

输入

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

输出

4
27