Laser

Jaehyun built a game a while back. It is called "Yoo Jaemin", and the hero of the game is Yoo Jaemin.

Yoo Jaemin fires laser beams from the origin $(0, 0)$. A beam is a ray that starts at the origin and travels outward in whatever direction the player picks. The goal is to hit as many of the segments on the coordinate plane as possible. Yoo Jaemin can fire the beam at most $K$ times, and a beam that only passes through an endpoint of a segment still counts as a hit.

Jaehyun left one case unhandled while writing the game: hitting a segment that has already been hit crashes the program. He panicked at first, then decided a game with that rule sounds fun anyway, so he wants to play it optimally. Find the largest number of segments he can hit without ever hitting the same segment twice.

The first line contains $K$ and $N$. ($1 \le K \le 100$, $1 \le N \le 500\,000$)

Each of the next $N$ lines contains one segment as $x_1$, $y_1$, $x_2$, $y_2$. ($1 \le x_1, y_1, x_2, y_2 \le 1\,000\,000$) The segment joins the point $(x_1, y_1)$ and the point $(x_2, y_2)$.

Print the largest number of segments that can be hit with at most $K$ laser beams, under the condition that a segment already hit is never hit again.