Có ~n~ con bò của người nông dân aihoi đang đứng ở các vị trí riêng biệt có tọa độ lần lượt là ~(x_1, y_1)\dots (x_n, y_n)~ ở trên trang trại hai chiều của anh ta ~(1 ≤ n ≤1000, x_i~ và ~y_i~ đều là các số nguyên dương lẻ có giá trị lớn nhất là ~1.000.000)~. aihoi muốn phân chia mảnh ruộng của anh ta bằng cách dựng một hàng rào bắc - nam dài (có độ dài là vô hạn) bằng phương trình ~x = a~ (~a~ sẽ là một số nguyên chẵn, do đó đảm bảo rằng anh ta không dựng hàng rào đi qua vị trí của bất kì con bò nào). Anh ta cũng muốn dựng một hàng rào đông - tây dài (có độ dài vô hạn) bằng phương trình ~y = b~ (với ~b~ là một số nguyên chẵn). Hai hàng rào giao nhau tại điểm có tọa độ ~(a, b)~ và cùng chia mảnh ruộng thành ~4~ miền. aihoi muốn chọn ~a~ và ~b~ sao cho số bò xuất hiện ở ~4~ miền là cân bằng, mà không có miền nào có quá nhiều con bò. Cho ~M~ là số bò lớn nhất có ở một trong ~4~ miền, aihoi muốn khiến ~M~ nhỏ nhất có thể.

Yêu cầu: Hãy giúp anh ta xác định giá trị nhỏ nhất của ~M~.

Input

• Dòng đầu gồm hai số nguyên dương ~N~;
• ~N~ dòng tiếp theo mỗi dòng chứa vị trí của từng con bò, xác định tọa độ ~x~ và ~y~.

Output

Đưa ra giá trị nhỏ nhất của ~M~ mà aihoi có thể đạt được khi xác định vị trí các hàng rào một cách tối ưu nhất.

Examples

Input

7
7 3
5 5
7 13
3 1
11 7
5 3
9 1

Output

2