UOJ Logo Sharp Sword 剑锋 OI

SSOI

#60. D硬币购物

统计

【问题描述】

一共有 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的方法总数,保证答案long long范围内。

【输入样例1】

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

【输出样例1】

4
27 

【数据范围】

100%的数据,d1,d2,d3,d4,s≤400,000 
30%的数据,tot≤500 
90%的数据,tot≤10000 
100%的数据,tot≤50000

【时空限制】

1S
256MB