硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。

　　第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s,其中di,s<=100000,tot<=1000

　　每次的方法数

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

int n,sum,flag,s;

ll f[100010];

ll ans;

int c[10],d[10];

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

void dfs(int x)

{

	if(x==5)

	{

		ans+=flag*f[s-sum];

		return ;

	}

	if(sum+c[x]*d[x]<=s)	sum+=c[x]*d[x],flag=-flag,dfs(x+1),sum-=c[x]*d[x],flag=-flag;

	dfs(x+1);

}

int main()

{

	int i,j;

	f[0]=1;

	for(i=1;i<=4;i++)

	{

		c[i]=rd();

		for(j=c[i];j<=100000;j++)	f[j]+=f[j-c[i]];

	}

	n=rd();

	for(i=1;i<=n;i++)

	{

		for(j=1;j<=4;j++)	d[j]=rd()+1;

		s=rd(),flag=1,ans=0;

		dfs(1);

		printf("%lld\n",ans);

	}

	return 0;

}