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 has two integers: l, n (l ≤ 20000 , n ≤ 500).

- Each of next n lines has two integers: 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 :)