Minimum Number of Hands

Emily is playing an arcade game on a machine with \(N\) buttons, numbered from \(1\) to \(N\) from left to right. The game requires her to press \(M\) buttons in sequence, one per second. At second \(T_i\), she must press button \(A_i\). Note that it is possible to have \(T_i = T_j\) and \(A_i = A_j\) for \(i \neq j\), meaning multiple presses can be required at the same time.

Each of Emily's hands can start at any button. Moving a hand from one button to an adjacent button takes exactly \(1\) second, and multiple hands can move simultaneously. The time to press a button is \(0\) seconds. Although an alien octopus could provide her with an infinite number of hands so that she could always achieve a perfect game, Emily is lazy and wants to use as few hands as possible. Your task is to determine the minimum number of hands \(S\) needed to complete the game.

In other words, given a sequence of events \((T_i, A_i)\), you need to cover all events with as few sequences (each representing a hand) as possible such that for any two consecutive events \((t, a)\) and \((T, A)\) in the same hand, it holds that \(T > t\) and \(|A - a| \leq T - t\).

inputFormat

The first line contains two integers \(N\) and \(M\), representing the number of buttons and the number of events, respectively.

Each of the following \(M\) lines contains two integers \(T_i\) and \(A_i\), indicating that at second \(T_i\), button \(A_i\) must be pressed.

outputFormat

Output a single integer \(S\), the minimum number of hands required to complete the game.

sample

5 3
1 3
3 5
4 4

1