[HAOI2008]硬币购物

Grade 0 Open Time Thursday, 21 February 2013, 11:02 pm
Discount 0.8 Time Discount Thursday, 28 February 2013, 11:02 pm
Allow late Yes Close Time Thursday, 28 February 2013, 11:02 pm
Input file coin.in Output file coin.out

【问题描述】

一共有 4 种硬币,面值分别为 c1,c2,c3,c4 。阿Q带着一些硬币去商店买东西,他带了d1枚第一种硬币,d2枚第二种硬币,d3枚第三种硬币,d4枚第四种硬币,若想买一个价值为s的东西,问阿Q有多少种付coins的方法。

比如 c={1,2,5,10},d={3,2,3,1},s=10,一共有4种方法:
10=1+1+1+2+5
10=1+2+2+5
10=5+5
10=10

注意,阿Q可能会去很多次商店,每次带的硬币数量和要买的东西价值可能不一样,你需要对每次都求出方法总数.

【数据输入】

输入文件的第一行是5个整数, c1,c2,c3,c4,tot 分别表示4种硬币的面值和阿Q去商店的次数,下面 tot 行 ,每行5个非负整数,d1,d2,d3,d4,s

【数据输出】

输出有tot行,表示第i次付coins的方法总数,保证答案在int64/long long范围内

【输入样例】
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

【输出样例】
4
27

【数据范围】

(1)100%的数据,d1,d2,d3,d4,s<=100,000

(2)30%的数据,tot<=50

(3)100%的数据,tot<=1000