Bessie đang ở trong một lưới hai chiều, nơi cô chỉ được phép đi theo các hướng song song với một trong hai trục tọa độ. Cô bắt đầu tại điểm \((0,0)\) và muốn đến \((N,N)\) (\(1\le N\le 10^9\)). Để giúp cô, trên lưới có \(P\) ván bật (\(1\le P\le 10^5\)). Mỗi ván bật nằm tại một điểm cố định \((x_1,y_1)\) và nếu sử dụng nó, Bessie sẽ đáp xuống điểm \((x_2,y_2)\).

Bessie là một cô bò luôn hướng tới phía trước, vì vậy cô chỉ cho phép mình đi lên hoặc sang phải, không bao giờ sang trái hay đi xuống. Tương tự, mỗi ván bật đều được thiết lập để không bao giờ đưa cô sang trái hay đi xuống. Khoảng cách nhỏ nhất Bessie cần đi bộ là bao nhiêu?

Phân nhóm

• Các test từ \(2\) đến \(5\) thỏa mãn \(P\le 1000\).
• Các test từ \(6\) đến \(15\) không có ràng buộc bổ sung.

Dữ liệu vào

Dữ liệu vào được đọc từ tệp boards.in.

Dòng đầu tiên chứa hai số nguyên \(N\) và \(P\), cách nhau bởi dấu cách.

Mỗi dòng trong \(P\) dòng tiếp theo chứa bốn số nguyên \(x_1\), \(y_1\), \(x_2\), \(y_2\), trong đó \(x_1\le x_2\) và \(y_1\le y_2\).

Tất cả vị trí ván bật và vị trí đích đều phân biệt.

Dữ liệu ra

Ghi ra tệp boards.out một số nguyên là khoảng cách nhỏ nhất Bessie cần đi bộ để đến \((N,N)\).

Ví dụ

3 2
0 1 0 2
1 2 2 3

3

Nguồn

• Kỳ thi: USACO 2020 January Contest, Gold
• Tên bài: Springboards
• Đề bài chính thức: https://usaco.org/index.php?page=viewproblem2&cpid=995
• Tác giả đề: Pedro Paredes