Nguồn đề: Beginner Free Contest 12

Đề bài: https://drive.google.com/file/d/1dp4k6EWJc6z8S-WgVTAr8J3NajsmVwDK/view?usp=sharing

Bài giải: https://drive.google.com/file/d/1mV3Lac3xh3i_hEKD1wKwTRrW7rgjIg5q/view?usp=sharing

Sau khi chinh phục mọi đỉnh cao về lập trình thi đấu toàn thế giới, Hải đã nghĩ đến việc rửa tay gác kiếm. Hải được Long chỉ điểm rằng có một đại lục màu mỡ mang tên Topcoder và liền đến đó xem thử tình hình. Đại lục được xem như là một mặt phẳng tọa độ, trên đó có một vườn cây N cây hoa Đăng Tiêu mọc lên, cây thứ i mọc ở ô ~(x_i, y_i)~.

Với sở thích code đẹp của Hải, anh nghĩ rằng mình nên dời một số cây đi và trồng lại vào một vị trí khác để N cây đó tạo thành một hàng dọc hoặc một hàng ngang trong đó các cây liên tiếp nhau và song song với hệ trục tọa độ. Việc di chuyển cây là vô cùng khó khăn và Hải chỉ có thể di chuyển tối đa một cây cùng lúc và mất 1 đơn vị thể lực để di chuyển cây đi một đơn vị. Hơn nữa, anh chỉ có thể di chuyển song song với hệ trục tọa độ.

Vì bận đi chơi nên Hải muốn nhờ các bạn giúp mình tìm các di chuyển cây trong vườn cây này sao cho lượng thể lực anh mất là nhỏ nhất có thể.

Input

Dòng 1: N số lượng cây hoa Đăng tiêu trong vườn cây ~(1 ≤ N ≤ 10^6).~

N dòng tiếp theo: mỗi dòng chứa 2 số nguyên ~x_i, y_i~ ~(-10^5 \leq x_i,y_i \leq 10^5)~ là tọa độ của cây thứ i.

Kết quả

Ghi ra một số nguyên duy nhất là lượng thể lực tối thiểu mà Hả cần để đạt được mong muốn của mình.

Sample Input 1

3
1 1
2 2
3 1

Sample Output 1

1

Sample Input 1

2 
1 1
1 3

Sample Output 1

1

Giải thích:

• Ở ví dụ 1: Có thể di chuyển cây ở vị trí (2, 2) sang vị trí (2, 1).

• Ở ví dụ 12: Có thể di chuyển cây ở vị trí (1, 1) sang vị trí (1, 2).