Description

There are some line segments in the plane. You may shoot at most $k$ rays starting from the origin to intersect as many segments as possible, and each segment may be counted at most once.

Find the maximum number of segments that can be intersected.

Input Format

The first line contains two integers $k$, $n$, where $n$ is the number of segments.
Then $n$ lines follow, each containing four integers $x_1, y_1, x_2, y_2$ describing a segment.

Output Format

Output a single integer, the maximum number of segments that can be intersected.

3 6
1 2 2 4
3 1 5 1
3 2 2 3
3 3 3 4
2 2 2 2
6 1 3 5

5

Hint

For $100\%$ of the testdata, $1 \leq k \leq 100$, $1 \leq n \leq 5\times10^5$, $1 \leq x_1, y_1, x_2, y_2 \leq 10^5$.

Translated by ChatGPT 5