题目描述

题目译自 XX Olimpiada Informatyczna — III etap Laser

Bajtazar 船长在 Tumulum VI 星球上狩猎线段兽。他的飞船停靠在着陆点（视为坐标系原点），装备了一门可旋转的眩晕激光炮。激光炮可朝任意角度发射，但飞船能源仅支持最多 $k$ 次射击，每次可选择任意角度。激光开启时无法旋转。

星球上有 $n$ 只线段兽，每只是一维生物（线段），端点位于正整数坐标。Bajtazar 的目标是用激光束击中尽可能多的线段兽，但每只线段兽只能被击中一次——他计划高价出售这些线段兽，因此它们必须保持身心完好。激光束沿直线传播，击中线段时会穿透并继续前行。即使激光束仅经过线段的端点或边缘，线段兽仍算被击中。

请编写程序，计算按照上述规则，最多能击中多少只线段兽。

输入格式

第一行包含两个整数 $k, n$ $(1 \leq k \leq 100, 1 \leq n \leq 500000)$，分别表示最大射击次数和线段兽数量。

接下来的 $n$ 行描述线段兽，每行包含四个正整数 $x_1, y_1, x_2, y_2$ $(1 \leq x_1, y_1, x_2, y_2 \leq 1000000)$，表示一只线段兽的端点坐标 $(x_1, y_1)$ 和 $(x_2, y_2)$。

输出格式

输出一行，包含一个整数，表示最多能用 $k$ 次激光射击击中（每只恰好一次）的线段兽数量。

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

只需发射两次激光即可。激光束在图中以虚线标示。

附加样例

1. $k=4, n=5$，小型正确性样例。
2. $k=2, n=5$，仅包含长度为零的线段兽。
3. $k=2, n=3$，特殊构造正确性样例。
4. $k=3, n=500000$，最大规模的样例。

数据范围与提示

对于 $36\%$ 的测试数据，$k \leq 2$。
对于 $45\%$ 的测试数据，$n \leq 2000$ 且 $k \leq 30$。
对于 $81\%$ 的测试数据，$n \leq 200000$ 且 $k \leq 50$。