死神有好多硬币!一分钱的,两分钱的,三分钱的,甚至是五千分钱的.死神有每种分值的硬币若干.死神要拿出一些硬币,使得和为S分.由于死神这一天特别开心,他还希望所选取的每种分值的硬币数量相等.因为死神打前一题数据的时候花费了太多的体力,现在意识模糊的他只能够算清楚一百以内的算术.
请告诉他,一共有多少种这样的可能方案.两种方案被认为是相同的,当且仅当每种分值面额硬币的选取数目相等.
接下来test块,每块第一行两个整数S,n,意指硬币面额和与不同面额硬币的数量;
紧接着n行,每行两个整数a,b,表示每种硬币的面额与数目;
对于100%的数据,test<=100,S<=5000,n<=50,a,b<=5000;
a互不相同,且保证使用long long答案大概也许应该与std无异.