Problem D
Crossy Boat

Tom wants to cross the ocean in one straight line. Unfortunately, every other ship is moving perpendicular to his direction. Thus, he tries to take notes of every ship’s position and length to avoid crashing with the other ships. Since Tom is not very fast in taking notes, he also notes down when the note was taken. All ships have a speed of $1$. While finishing the latest note(s), Tom immediately starts his journey.

Tom imagines the sea as an endless Cartesian plane with his house at $(0, 0)$. Tom has a boat that is integer $l$ in length and a speed of $1$.

Tom can start his journey with the head of his ship on any non-negative integer coordinate on the $x$-axis, i.e. any coordinate $(a, 0)$ where integer $a \geq 0$. The ship goes parallel to the $y$-axis (such that the tail of his ship trails behind him for length $l$), while every other ship is moving parallel to the $x$-axis towards the left.

All ships are considered as lines without any width. A collision occurs when the line of Tom’s ship occupies the same point as any of the other ships on the ocean. If any of the ships on the ocean would overlap, consider the ships to slide past each other without affecting their movement. (Since the ships are parallel lines with zero width, they are allowed to avoid a collision with an infinitesimally small adjustment.)

Help Tom find the minimum integer $x$-coordinate of the point he can start at so that his journey to the other side of the sea is a straight line.

Input

First line of input contain the integer length $l$ of Tom’s ship ($1 \leq l \leq 10^9$), and the number of notes Tom has written down $n$ ($1 \leq n \leq 1000$). For the next $n$ lines, we have the entries of the notes, each of which contains four integers:

• $0 \leq t_ i \leq 10^9$: the time the note was taken

• $0 \leq x_ i, y_ i \leq 10^9$: the coordinates of the head of the ship

• $1 \leq w_ i \leq 10^9$: the length of the ship

Tom is a messy writer, so the list is not written in order (such that the latest note(s) may have been written in the middle of the list).

Output

The minimum integer $x$-coordinate of the point Tom can start after the last note so that his path across the ocean is a straight line without any collision.

1 2
0 1 0 1
0 5 0 1

3

1 1
0 0 0 4

5

2 2
0 12 3 1
3 0 0 2

3