BLUEEQ2 - Help Blue Mary Please! (Act II)
Today Mary's math homework is to solve an equation.
She knows all ki and pi, and 1<=xi<=M. All xi must be integers. She must work out the number of different solutions of this equation this day.Can you give her a hand?
There is a single integer T in the very first line of the input denoted the number of tests.T blocks follow.
For each test case:
The first line contains a single integer n(n<=6).The second line contains a single integer m(m<=150).n lines follow,each contains two space-separated integers ki and pi, i=1,2,...,n. All pi are positive.
For each test case output a single line ,which contains a single integer - the answer.You may assume this number is less than 2^31.
Input: 1 3 150 1 2 -1 2 1 2 Output: 178
Warning: The time limit is very strict for this problem.