Giải bài trực tuyến

Nam và Bắc là hai bạn rất ham chơi trò chơi trên máy tính, đặc biết là trò chơi có tên “ Robốt gom châu báu”. Trò chơi được thể hiện trên một lưới ô vuông đơn vị vô hạn, trên đó có một số ô vuông chứa châu báu và một robốt ban đầu đứng tại một ô nào đó mà bạn chọn. Cần điều khiển rôbốt tới các ô chứa châu báu và nhặt châu báu tại các ô đó. Trên bàn phím bạn được chọn 8 phím để di chuyển rôbốt tương ứng với 8 hướng sang 8 ô kề với ô hiện thời của robốt. Nếu bạn có 8 hướng thì việc bạn điều khiển rôbốt để nhận được tất cả châu là chuyện tầm thường. Tuy nhiên do sử dụng máy tính chơi quá nhiều nên bàn phím của hai bạn đã bị liệt hầu hết các phím.

Yêu cầu

Với một trạng thái của lưới ô vuông cho trước, hãy xác định số phím tối thiểu cần sử dụng sao cho bạn có thể chọn vị trí xuất phát của rôbốt và chỉ dùng các phím đã chọn theo các hướng tương ứng để nhặt hết châu báu.

Dữ liệu

Dòng đầu chứa số N là số vị trí ô chứa châu báu (N≤1000). Dòng thứ i trong N dòng tiếp theo, mỗi dòng chứa hai số nguyên là tọa độ của ô chứa châu báu. Các số nguyên đều có trị tuyệt đối không quá 100000.

Kết quả

Ghi ra một số nguyên duy nhất là số phím ít nhất cần sử dụng.

Ví dụ

Dữ liệu
4
0 0
0 2
2 0
2 2

Kết quả
2

Dữ liệu
4
-1 0
2 0
2 2
0 2

Kết quả
2

Nguồn: Цикл Интернет-олимпиад для школьников, сезон 2008-2009