Special Oreum Climb

Oreum must be climbed.

The name of the NLCS Jeju dormitory, "Oreum," comes from the Jeju word for a peak or mountain. Once a year, the students of each dormitory climb the oreum that gave their dormitory its name.

The oreum is a triangle with vertices $(0, 0)$, $(N, N)$, and $(2N, 0)$ in the $xy$ plane. You start at $(0, 0)$ and must reach $(2N, 0)$.

From $(x, y)$, you can move only to $(x+1, y+1)$ or $(x+1, y-1)$. Every position you arrive at must be inside the oreum or on its boundary.

It is easy to get lost on the oreum, so teachers are stationed at $M$ points where people tend to lose their way. You have not done your homework, so you do not want to meet a teacher. Move while avoiding the teachers.

You also decide to take photos to make the climb memorable. A photo is more beautiful when it is taken at a higher point. Specifically, the $y$ coordinate of the place where the photo is taken is its beauty score. Find the maximum beauty score of a photo you can take.

The first line contains $N$, the height of the oreum, and $M$, the number of points where teachers are, separated by a space.

Lines 2 to $M+1$ each contain the $x$ coordinate $x\_i$ and the $y$ coordinate $y\_i$ of a teacher, separated by a space. Every teacher is inside the oreum or on its boundary.

Print the maximum beauty score of a photo you can take on the first line. If you cannot travel from the start to the destination, print -1.

• $1 \le N \le 1\,000$
• $0 \le M \le \min\left(\frac{(N+1)(N+2)}{2} - 1, 100\,000 \right)$
• $0 \le x\_i \le 2N$
• $0 \le y\_i \le N$
• $x\_i + y\_i$ is even.
• There is no teacher at $(0,0)$.