James loves drinking soup, specifically, magical soup. However, being the connoisseur of soup that he is, he is a picky drinker — meaning that his soup must be up to his standards. In particular, every time he drinks soup, it must satisfy the following conditions:
- The temperature of each bowl of soup must be no more than ~X~ when he drinks it, or his mouth will get burned. Each bowl of soup starts at some integer temperature ~T_i~ and cools down by ~1~ unit at the end of each minute.
- Each bowl of soup must also be at most ~F_i~ minutes old when he drinks it. It isn't fresh enough for him after that.
James starts out with ~N~ bowls of fresh, new, zero-minute-old soup. Every minute, he can consume at most one bowl of soup. Can you find out the maximum amount of bowls of soup he can drink?
For all subtasks:
~0 \le X, N, T_i, F_i \le 500\,000~
Subtask 1 [10%]
~0\le X, N, T_i, F_i \le 100~
Subtask 2 [90%]
No additional constraints.
The first line will contain 2 integers ~X~ and ~N~, representing James' temperature threshold and the number of bowls of soup.
The following ~N~ lines will each contain two integers ~T_i~ and ~F_i~, denoting the starting temperature of each bowl of soup and the amount of time the soup must be consumed in.
Output one integer, the maximum number of bowls of soup James can drink.
Sample Input 1
1 3 3 2 5 1 2 3
Sample Output 1
Explanation for Sample Output 1
James can wait ~1~ minute to drink the third bowl of soup as the temperature of the soup cools down to ~1~. He can wait another minute to drink the first bowl. The second bowl will expire after ~1~ minute, but the bowl is still too hot so he cannot drink it.
Sample Input 2
20 5 100 91 30 10 69 10 20 1 1 2
Sample Output 2