Ông JOI có một chiếc bàn rất lớn trong phòng trưng bày bộ sưu tập, trên đó đặt nhiều đồng xu quý hiếm. Để dọn bàn, ông muốn sắp xếp lại các đồng xu.

Chiếc bàn được xem như một lưới gồm \(2000000001 \times 2000000001\) ô. Các cột được đánh số từ \(-10^9\) đến \(10^9\) từ trái sang phải, còn các hàng được đánh số từ \(-10^9\) đến \(10^9\) từ dưới lên trên. Ô ở cột \(x\), hàng \(y\) được ký hiệu là \((x,y)\).

Có \(2N\) đồng xu. Ban đầu, đồng xu thứ \(i\) nằm tại ô \((X_i,Y_i)\). Mục tiêu của ông JOI là đặt một đồng xu vào mỗi ô \((x,y)\) thỏa mãn \(1 \le x \le N\) và \(1 \le y \le 2\).

Để tránh làm hỏng đồng xu, thao tác duy nhất ông có thể thực hiện là chọn một đồng xu rồi chuyển nó sang một ô kề cạnh. Hai ô kề cạnh khi và chỉ khi chúng có chung một cạnh. Trong quá trình di chuyển, nhiều đồng xu được phép nằm trên cùng một ô.

Hãy tính số thao tác ít nhất cần thực hiện để đạt được mục tiêu.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng:

N
X_1 Y_1
...
X_{2N} Y_{2N}

Dữ liệu ra

In ra một dòng chứa số thao tác ít nhất cần thực hiện.

Ràng buộc

• Các giá trị đầu vào đều là số nguyên.
• \(1 \le N \le 100000\).
• \(-10^9 \le X_i,Y_i \le 10^9\) với \(1 \le i \le 2N\).

Phân nhóm

1. \(8\) điểm: \(1 \le N \le 10\); \(-10^9 \le X_i,Y_i \le 10^9\) với \(1 \le i \le 2N\).
2. \(29\) điểm: \(1 \le N \le 1000\); \(-10^9 \le X_i,Y_i \le 10^9\) với \(1 \le i \le 2N\).
3. \(63\) điểm: \(1 \le N \le 100000\); \(-10^9 \le X_i,Y_i \le 10^9\) với \(1 \le i \le 2N\).

Ví dụ

3
0 0
0 4
4 0
2 1
2 5
-1 1

15

4
2 1
2 1
2 1
3 1
3 1
3 1
3 1
3 1

9

5
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
-1 -5
-2 2
2 8
4 7
-2 5
7 3

8000000029

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2018/2019, bài 4. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.