507002 - 硬币购物

【题目描述】硬币购物(shopping)

某人去超市购物,去了n次,想购买s的价值的东西。他共有4种硬币,面值分别为c1,c2,c3,c4。对于每次购买,他带了di枚i种硬币,试计算每次有多少种付款方法。

输入

输入的第一行是五个整数,分别代表c1,c2,c3,c4,n(1≤ci,di,s≤¥10^5$,1≤n≤1000)。 接下来n行,每行有五个整数,描述一次购买,分别代表d1,d2,d3,d4,s。

输出

对于每次购买,输出一行一个整数代表答案。

样例

输入

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

输出

4
27
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题