THỰC HÀNH

Xét lưới ô vuông tạo thành từ n×n đường, các đường của lưới được đánh số từ 1 đến n từ trái qua phải và từ trên xuống dưới. Ở mỗi hàng thứ i, người ta cho đoạn thẳng xác định bởi hai điểm l_i và r_i.

Yêu cầu: Xác định độ dài của đường đi ngắn nhất dọc theo các cạnh của lưới từ điểm (1,1) đến điểm (n, n) và thoả mãn các điều kiện:

• Chỉ đi sang phải, sang trái hoặc xuống dưới
• Đi qua tất cả các điểm thuộc các đoạn thẳng đã cho.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương n.
• Dòng thứ i trong n dòng tiếp theo chứa hai số nguyên dương l_i, r_i (hai số được ghi cách nhau một dấu cách).

Dữ liệu ra:

Ghi ra một số nguyên duy nhất là độ dài của đường đi ngắn nhất tìm được.

Ví dụ:

Dữ liệu vào:
6
2 6
3 4
1 3
1 2
3 6
4 5

Dữ liệu ra:
24

Giải thích: Lưới đề bài và đường đi (màu xanh) như hình dưới (Đoạn có nét kép là đi lặp lại 2 lần).

Giới hạn: 1 ≤ n ≤ 20000; 1 ≤ l_i ≤ r_i ≤ n.