{"code":"usaco16febplatp1","name":"USACO 2016Feb Platinum - Load Balancing","description":"Bác nông dân John có $N$ chú bò đang đứng ở các vị trí khác nhau đôi một $(x_1, y_1), (x_2, y_2), \\dots, (x_n, y_n)$ trên một cánh đồng hai chiều $(1 \\leq N \\leq 100\\ 000$, và $x_i, y_i$ là các số nguyên dương lẻ có giá trị tối đa $1\\ 000\\ 000)$. Bác John muốn chia cánh đồng bằng cách dựng lên một hàng rào bắc-nam dài vô hạn theo đường thẳng $x=a$ (a là một số nguyên chẵn, để đảm bảo không cắt ngang con bò nào). Ông cũng muốn dựng lên một hàng rào dài vô hạn khác theo hướng đông-tây theo phương trình đường thẳng $y=b$, với $b$ là một số nguyên chẵn. Hai hàng rào này giao nhau tại điểm $(a, b)$, và chúng chia cánh đồng thành bốn vùng.\r\n\r\nBác John muốn chọn $a$ và $b$ sao cho số lượng bò xuất hiện ở bốn vùng sẽ tương đối \"cân đối\", với không có vùng nào chứa qúa nhiều bò. Gọi $M$ là số lượng bò tối đa xuất hiện ở 1 trong 4 vùng, bác muốn giá trị $M$ càng nhỏ càng tốt. Hãy giúp bác ấy tìm ra giá trị nhỏ nhất của $M$.\r\n\r\n#### Dữ liệu đầu vào\r\n - Dòng đầu tiên chứa một số nguyên dương $N$.\r\n - $N$ dòng tiếp theo, mối dòng chứa hai số $x_i, y_i$ biểu diễn địa điểm của từng chú bò.\r\n\r\n#### Định dạng đầu ra\r\n - In ra giá trị $M$ nhỏ nhất mà bác John có thể đạt được bằng cách chọn vị trí của hàng rào một cách tối ưu.\r\n\r\n#### Ví dụ\r\n!!! question \"Ví dụ 1\"\r\n    ???+ \"Đầu vào\"\r\n        ```sample\r\n        7\r\n        7 3\r\n        5 5\r\n        7 13\r\n        3 1\r\n        11 7\r\n        5 3\r\n        9 1\r\n        ```\r\n    ???+ success \"Đầu ra\"\r\n        ```sample\r\n        2\r\n        ```","points":1.0,"partial":false,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}