시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 0 0 0 0.000%

문제

Kapitan Bajtazar poluje na odcinkowce na planecie Tumulum VI. Jego statek stoi w miejscu lądowania (które będziemy uważać za początek układu współrzędnych) i wyposażony jest w laser ogłuszający. Laserem tym można obracać, tak aby promień lasera był skierowany pod dowolnym kątem. Zasilania statku wystarczy na co najwyżej  strzałów, z których każdy może być oddany pod dowolnie wybranym kątem. W momencie, gdy laser jest włączony, nie można nim obracać.

Na planecie znajduje się  odcinkowców - każdy z nich jest istotą jednowymiarową (odcinkiem) o końcach w punktach o współrzędnych dodatnich i całkowitych. Celem Bajtazara jest trafienie promieniem lasera jak największej liczby odcinkowców, przy czym zabronione jest trafienie jakiegoś odcinkowca więcej niż raz - kapitan chce je sprzedać z dobrym zyskiem, a do tego muszą być w nienagannym stanie fizycznym i psychicznym. Promień lasera rozchodzi się wzdłuż prostej, a gdy trafia odcinek, przenika przez niego i biegnie dalej. Jeśli promień lasera przejdzie przez sam koniec lub wzdłuż odcinkowca, to również jest on trafiony.

Napisz program, który wyznaczy maksymalną liczbę odcinkowców, które można trafić promieniem lasera, zgodnie z podanymi powyżej zasadami.

입력

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite k i n (1 ≤ k ≤ 100, 1 ≤ n ≤ 500 000), oddzielone pojedynczym odstępem. W kolejnych wierszach opisane są odcinkowce, po jednym w wierszu. W każdym z tych wierszy znajdują się po cztery dodatnie liczby całkowite x1, y1, x2, y2 (1 ≤ x1, y1, x2, y2 ≤ 1 000 000), rozdzielone pojedynczymi odstępami. Liczby takie reprezentują odcinkowca o końcach (x1, y1) i (x2, y2).

출력

Twój program powinien wypisać w pierwszym (i jedynym) wierszu standardowego wyjścia dokładnie jedną liczbę całkowitą: maksymalną liczbę odcinkowców, które można trafić promieniem lasera (każdego dokładnie raz), wykonując co najwyżej k strzałów.

예제 입력

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

힌트