Cho bảng gồm n hàng và m cột. Trong cột j, các ô đen liên tiếp từ hàng sⱼ đến hàng tⱼ; những ô còn lại có màu trắng.

Mỗi bước chọn một cột và dịch toàn bộ đoạn ô đen trong cột đó lên hoặc xuống một hàng, sao cho đoạn vẫn nằm trong bảng. Độ dài đoạn ô đen không thay đổi.

Một bảng được gọi là đẹp nếu tất cả các ô đen tạo thành một miền liên thông theo cạnh. Tìm tổng số bước dịch ít nhất để bảng trở nên đẹp.

Dữ liệu vào

Dòng đầu chứa n, m (1 ≤ n, m ≤ 10⁵, n × m ≤ 10⁶).

m dòng tiếp theo, dòng j chứa sⱼ, tⱼ (1 ≤ sⱼ ≤ tⱼ ≤ n).

Kết quả

Một số nguyên là số bước ít nhất.

Ví dụ

Input

9 3
1 2
4 5
7 9

Output

4

Đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn. Mỗi test được chấm độc lập.