G. Goombas Colliding
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Atsa just bought Super Mario Maker and wants to test your skills for an analysis with a level that he prepared.

That level consists of a platform with some Goombas in it. As you know, Goombas are characters with the following behavior:

  • Initially, they point in one direction, (left: 0, right: 1).
  • They move in the direction they are currently facing, as long as there are no obstacles.
  • If two Goombas collide, they will flip their direction inmediately.
  • When a Goomba reaches one end of the platform, it falls.

The platform is $$$L$$$ blocks long, extending from the coordinate $$$0$$$, to $$$L$$$. Above it, there will be $$$G$$$ Goombas. The $$$i-th$$$ Goomba will be located at $$$p_i$$$ facing to the direction $$$d_i$$$. All Goombas will advance with a speed of $$$1$$$ block per second.

Atsa wants you to tell him how many seconds it will take for the platform to be empty.

For this problem purposes, consider the size of a Goomba to be a single point. No two Goombas will share the same initial $$$x$$$ coordinate.

Input

The first line of the input contains two integers $$$L$$$ $$$\left(2\leq L \leq 10^{16}\right)$$$ and $$$G$$$ $$$\left(1 \leq G \leq 10^4 \right)$$$.

Each of the following $$$G$$$ lines contains two integers $$$p_i$$$ $$$\left(0 < p_i < L\right)$$$ and $$$d_i$$$ $$$\left(d_i \in \{0, 1\}\right)$$$.

Output

The time in seconds that must pass for the platform to be empty.

Examples
Input
3 2
1 1
2 0
Output
2
Input
5 2
1 0
2 1
Output
3