Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Sau chiến thắng của vùng đất Trung địa, nhà vua quyết định ban thưởng cho các tướng quân. Bên cạnh vàng bạc, châu báu, nhà vua ban thưởng thêm cả đất đai. Có một hòn đảo ở ven biển, nhà vua đem chia đất đều cho N tướng quân.

Một cận thần của nhà vua cho biết rằng, trên hòn đảo đã có sẵn một số dòng sông. Điều đặc biệt là các dòng sông này chảy thẳng tắp theo một hướng nhất định. Ông không nhớ có chính xác tất cả bao nhiêu con sông, nhưng ông nhớ một số khúc sông nhất định (có đủ của tất cả các dòng sông trên đảo), là các vị trí mà ông đã từng khảo sát.

Chia đất như thế này có vẻ dễ rơi vào tình trạng không đều, nhà vua đang băn khoăn. Nhưng tất cả các tướng quân đều bảo rằng diện tích của mình là bao nhiêu không quan trọng, miễn là họ có đường biển là được. Vì vậy, nhà vua quyết định vẽ thêm một số ranh giới, cũng là đường thẳng, để có thể phân chia đủ đất cho tất cả các tướng quân.

Coi hòn đảo có diện tích là vô hạn. Các bạn hãy tính toán giúp nhà vua xem cần phải vẽ thêm bao nhiêu đường ranh giới, để có thể làm hài lòng tất cả các tướng quân.

Input

Dòng đầu tiên gồm 2 số nguyên N và K (1 <= N, K <= 100) lần lượt là số tướng quân và số khúc sông mà cận thận của nhà vua đã khảo sát.

K dòng tiếp theo, mỗi dòng gồm 4 số nguyên xA, yA, xB, yB (có giá trị tuyệt đối <= 10^6) là tọa độ biểu diễn 2 điểm thể hiện khúc sông mà người cận thần đã khảo sát.

Output

In ra một số nguyên duy nhất là số đường ranh giới nhà vua cần phải bổ sung vào bản đồ của hòn đảo.

Example

Test 1:

Input:

2 1
1 1 -2 0

Output:

0

Giải thích test 1: Có 1 con sông trên đảo, nó chia hòn đảo thành 2 miền, và vừa đủ số vùng đất
cho 2 tướng quân của nhà vua.

Test 2:

Input:

5 3
0 5 5 5
0 0 1 1
2 2 3 3

Output:

1