[HAOI2008] 硬币购物

• 时间限制：1 秒
• 内存限制：128 MiB

题目描述

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

共有 $n$ 次购物。每次购物给出 $d_1,d_2,d_3,d_4,s$：第 $i$ 种硬币至多使用 $d_i$ 枚，需要支付的总面值恰好为 $s$。

对于每次购物，求满足

$$c_1x_1+c_2x_2+c_3x_3+c_4x_4=s, \qquad 0\le x_i\le d_i$$

的整数四元组 $(x_1,x_2,x_3,x_4)$ 数量。

输入格式

第一行五个整数 $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

数据范围

对于所有数据，$1\le c_i,d_i,s\le10^5$，$1\le n\le1000$。

子任务编号	分值	特殊限制
1	20	对所有询问均有 $s\le2000$
2	40	对所有询问均有 $d_3=d_4=1$
3		无特殊限制

本题采用独立测试点计分。