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:
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
Name |
---|