P3562 [POI 2013] LAS-Laser

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.

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 a single integer, the maximum number of segments that can be intersected.

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