P0412

[HAOI2008]硬币购物

一共有 44 种硬币，面值分别为 c1,c2,c3,c4c_1, c_2, c_3, c_4。

某人去商店买东西，一共去了 tottot 次。第 ii 次他带了第 jj 种硬币各 djd_j 枚（j=1,2,3,4j=1,2,3,4），要买价值为 ss 的东西。

请问每次购物有多少种付款方法。两种付款方法不同，当且仅当至少有一种硬币的使用枚数不同。

输入格式

第一行包含五个正整数 c1,c2,c3,c4,totc_1, c_2, c_3, c_4, tot，分别表示四种硬币的面值和购物次数。

接下来 tottot 行，每行包含五个非负整数 d1,d2,d3,d4,sd_1, d_2, d_3, d_4, s，表示这次购物携带的四种硬币枚数和要购买的物品价值。

输出格式

对每次购物输出一行一个整数，表示付款方法数。

样例输入

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

样例输出

4
27

样例解释

四种硬币的面值为 1,2,5,101, 2, 5, 10，共购物两次。

第一次带 11 元硬币 33 枚、22 元硬币 22 枚、55 元硬币 33 枚、1010 元硬币 11 枚，要凑出 1010 元，共有 44 种方法。

数据范围

对于所有测试数据：

  • 1≤tot≤10001\le tot\le 1000；
  • 1≤cj≤1051\le c_j\le 10^5；
  • 0≤dj≤1050\le d_j\le 10^5；
  • 0≤s≤1050\le s\le 10^5。

来源与许可

本题为 HAOI 2008 试题「硬币购物」，题面与测试数据整理自 BZOJ 1042。