Problem G - Coin Changing Again
There are four types of coins with value c1, c2, c3 and c4, and there are only d1, d2, d3 and d4 number of these coins respectively. How many ways are there to obtain a value v by adding up these coins?
For example, if you have 3 $1-coins, 2 $2-coins, 3 $5-coins, 1 $10-coin, there are 4 ways to obtain $10 from those coins:
10 = 1 + 1 + 1 + 2 + 5
10 = 1 + 2 + 2 + 5
10 = 5 + 5
10 = 10
Input
The input begins with an integer N (≤ 100) which indicates the number of test cases followed. Each of the following test cases begins with five positive integers c1, c2, c3, c4, q, where 1 ≤ c1 < c2 < c3 < c4 ≤ 1000 and q ≤ 100. It is then followed by q queries. Each query consists of 5 integers, d1, d2, d3, d4, v, where 1 ≤ d1, d2, d3, d4, v ≤ 105.
Output
For each query from each test case, print out the number of way to obtain v by adding up d1 c1-coins, d2 c2-coins, d3 c3-coins and d4 c4-coins in a single line.
Sample input
2
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
10 20 30 40 1
100 100 100 100 101
Sample output
4
27
0
Problem setter: Cho
Source: Tsinghua-HKUST Programming Contest 2007