Yk is a archaeologist. When discovering the pyramids of Egypt, he found a treasure map which show the location of n secret islands, each island has only a kind of precious stone, with the weight m[i](kg) and the quantity s[i].

So he decided to buy a plane to look for the  treasure. But he just hired a small plane which carrying the maximum of l(kg).

So he want to know how many ways to select the stones which fill the plane? (total of the weight of the stones is l).

Input

-         The first line is two integer: l,n (l<=20000 , n<=500).

-         Each of next n line is two integer: m[i],s[i] (m[i]<=5000 , s[i]<=100).

Output

-         Only line is your answer.

Example

Input:
10 3
4 7
4 5
2 5

Output:
6

Note: you must optimize your code to get AC, time limit will be 11s :)