題目地址：http://acm.hdu.edu.cn/showPRoblem.php?pid=2079

/************************************************************************

此題深搜即可，但要剪枝，否則超時。

/***************************************************dfs

代碼如下：

/***********************

#include<stdio.h>int n,k,T;int a[9][2];int count;void dfs(int start,int sum){	if(sum==n)	{		count++;		return ;	}	if(start>=k||sum>n)	{		return ;	}	for(int i=0;i<=a[start][1];i++)	{		dfs(start+1,sum+i*a[start][0]);	}}int main(){	scanf("%d",&T);	while(T--)	{		scanf("%d%d",&n,&k);		for(int i=0;i<k;i++)		{			scanf("%d%d",&a[i][0],&a[i][1]);		}		count=0;		dfs(0,0);		printf("%d/n",count);	}	return 0;}