은하 군벌

드디어 은하에 평화가 찾아올까요? 모든 군벌이 우주를 나눠 갖기 위해 한자리에 모였습니다. 협상이 상당히 진전되어, 군벌들은 누가 어느 영역을 차지할지 평화롭게 결정하는 방법에 합의했습니다.

먼저 2차원 은하 지도를 여러 개의 무한한 직선으로 잘라 구역(sector)으로 나눕니다. 함대가 가장 큰 군벌이 구역 하나를 고르고, 그다음으로 함대가 큰 군벌이 다른 구역 하나를 고르는 식으로, 모든 군벌이 구역을 하나씩 차지할 때까지 진행합니다. 이 과정을 남은 구역이 없을 때까지 반복합니다.

어떤 군벌도 다른 군벌보다 좁은 영역에 만족하지 않으므로, 모두가 정확히 같은 넓이를 가져야만 평화가 유지됩니다. 우주는 무한하고 따라서 지도도 무한하므로, 넓이가 무한한 구역이 존재합니다. 모두가 원하는 것은 바로 이 무한한 넓이입니다. 당신은 제안된 분할에 무한한 직선을 추가로 그을 수 있습니다. $W$명의 군벌이 각자 넓이가 무한한 구역을 최소 하나씩 차지할 수 있도록 하려면, 최소 몇 개의 직선을 추가로 그어야 하는지 구하세요.

첫째 줄에 두 양의 정수 $W$와 $N$이 주어집니다 ($1 \le W, N \le 100$). 각각 군벌의 수와 제안된 분할에 포함된 직선의 개수입니다. 이어지는 $N$개의 줄에는 각각 네 정수 $x_1$, $y_1$, $x_2$, $y_2$가 주어지며(각 절댓값은 $10000$ 이하), 이는 지도 위의 서로 다른 두 점 $(x_1, y_1)$과 $(x_2, y_2)$를 지나는 직선 하나를 나타냅니다.

모든 군벌을 만족시키기 위해 제안에 추가로 그어야 하는 직선의 최소 개수를 정수 하나로 출력하세요.