408043: GYM102966 G Goombas Colliding

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.

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)$$$.

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

3 2
1 1
2 0

2

5 2
1 0
2 1

3