Coin Combinations and Queries

Time limit3sMemory limit512 MB

Summary

For each query, count the multisets of at most d_i coins of denomination c_i (i=1..4) that sum to exactly v; answers fit in 64-bit.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

A country issues coins of exactly four denominations, worth $c_1$ , $c_2$ , $c_3$ and $c_4$ won. Your wallet holds $d_1$ coins worth $c_1$ won, $d_2$ coins worth $c_2$ won, $d_3$ coins worth $c_3$ won and $d_4$ coins worth $c_4$ won. Write a program that counts the ways to pay exactly $v$ won with those coins.

Coins of the same denomination are not distinguished. Two ways are the same when they use the same number of coins of every denomination.

For example, with three 1 won coins, two 2 won coins, three 5 won coins and one 10 won coin, there are four ways to pay 10 won.

$10 = 1 + 1 + 1 + 2 + 5$
$10 = 1 + 2 + 2 + 5$
$10 = 5 + 5$
$10 = 10$

Input

The first line contains the number of test cases $T$ . ( $1 \le T \le 100$ )

The first line of each test case contains the integers $c_1$ , $c_2$ , $c_3$ , $c_4$ , $q$ separated by spaces. ( $1 \le c_1 < c_2 < c_3 < c_4 \le 1000$ , $1 \le q \le 100$ )

Each of the next $q$ lines contains one query, made of the integers $d_1$ , $d_2$ , $d_3$ , $d_4$ , $v$ . ( $1 \le d_1, d_2, d_3, d_4, v \le 10^5$ )

Output

For each query, print on its own line the number of ways to pay exactly $v$ won using at most $d_1$ coins of $c_1$ won, at most $d_2$ coins of $c_2$ won, at most $d_3$ coins of $c_3$ won and at most $d_4$ coins of $c_4$ won. Print 0 when no way exists. The answer can exceed the range of a 32-bit integer.

Examples2

Example 1

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

Expected output

4
27
0

Example 2

Input

3
1 2 3 4 3
1 1 1 1 10
1 1 1 1 5
1 1 1 1 1
2 4 6 8 2
5 5 5 5 7
5 5 5 5 8
5 10 20 50 2
3 3 3 3 100
1 1 1 1 4

Expected output