Bajtazar 船长正在 Tumulum VI 星球上狩猎“线段生物”。他的飞船停在着陆点（我们将其视为坐标系原点），并配备了一台眩晕激光器。激光器可以旋转，使激光束指向任意角度。飞船的能量最多支持 $k$ 次射击，每次射击都可以选择任意角度。激光器开启后，在射击过程中无法旋转。

星球上有 $n$ 个线段生物，每一个都是一维生物（线段），其端点坐标均为正整数。Bajtazar 的目标是用激光束击中尽可能多的线段生物，且每个线段生物最多只能被击中一次——船长想以高价出售它们，因此它们必须保持良好的生理和心理状态。激光束沿直线传播，当它击中一条线段时，会穿过它并继续前进。如果激光束穿过线段的端点或沿着线段本身射出，也视为击中。

请编写一个程序，根据上述规则计算出激光束最多能击中的线段生物数量。

输入格式

第一行包含两个整数 $k$ 和 $n$ ($1 \le k \le 100, 1 \le n \le 500\,000$)，用空格分隔。接下来的 $n$ 行，每行描述一个线段生物。每行包含四个正整数 $x_1, y_1, x_2, y_2$ ($1 \le x_1, y_1, x_2, y_2 \le 1\,000\,000$)，用空格分隔，表示线段的两个端点 $(x_1, y_1)$ 和 $(x_2, y_2)$。

在分值占 36% 的测试点中，满足额外条件 $k \le 2$；在分值占 45% 的测试点中，满足 $n \le 2\,000$ 且 $k \le 30$；在分值占 81% 的测试点中，满足 $n \le 200\,000$ 且 $k \le 50$。

输出格式

程序应在标准输出的第一行（也是唯一一行）输出一个整数：在最多进行 $k$ 次射击的情况下，能够击中的线段生物的最大数量（每个线段生物最多被击中一次）。

样例

输入 1

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

输出 1

5

说明 1

样例说明：只需发射两次激光。激光束在图中用虚线表示。