文理学院程序设计在线练习


交换卡片

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 62   Accepted Submission(s): 37
Problem Description

作为篮球爱好者, 小明喜欢收集篮球运动员的卡片. 但作为学生,他不可能花钱去买新的卡片, 因此,有时会和朋友交换卡片. 当然, 不同的卡片具有不同的价值, 小明只能用自己已经拥有的卡片去交换新的卡片. 例如, 为了获得一张价值为10的卡片, 他可以使用2张价值为5的卡片或者3张价值为3的卡片加上1张价值为1的卡片, 这取决于小明自己拥有的卡片情况. 甚至有时因为无法组合出恰当的价值而无法交换(因为交换必须严格满足等价的原则).
给出小明需要交换的新的卡片的价值,以及现在已经拥有的卡片情况, 求出可以进行等价交换的方式总数.

Input

输入数据首先包含一个整数T,表示测试实例的个数,然后是T组测试数据。
每组测试数据首先包含2个整数,分别表示需要交换的新卡片的价值n(1<=n<=1000),以及现在已经拥有的不同的卡片种类m(1<=m<=10)。然后是m行数据,每行2个整数val, num,分别表示每种卡片的价值和小明当前拥有的该类卡片的数量。
注意: 假设不同类型的卡片具有不同的价值, val和num 是大于0的整数。你可以假设运行过程不会超出int型的数据范围。

Output

对于每组测试数据, 输出可以进行等价交换的方式总数。

Sample Input
2
5 2
2 1
3 1
10 5
10 2
7 2
5 3
2 2
1 5
Sample Output
1
7
Source

zscas计算机知识竞赛2008/11/03