Thành phố Nồi Hạ có phân bổ dân cư hết sức đặc biệt: Thành phố có khu dân cư được xếp dưới dạng lưới hình chữ nhật gồm hàng và cột. Các hàng được đánh số từ đến , các cột được đánh số từ đến . Khu dân cư nằm trên giao của hàng và cột được kí hiệu là .
Trong đợt khảo sát vừa qua, lãnh đạo thành phố đã đi từng ngõ, gõ từng nhà để thu thập thông tin về chất lượng cuộc sống ở các khu dân cư. Tiếp đó, họ xếp hạng các khu dân cư bằng các con số phân biệt từ đến . Khu dân cư xếp hạng có chất lượng cuộc sống tốt nhất. Khu dân cư xếp hạng có chất lượng tệ nhất. Khu dân cư được xếp hạng càng nhỏ thì chất lượng sống càng cao. Theo kết quả, khu dân cư được xếp hạng .
Từ kết quả xếp hạng, thành phố sẽ chọn ra một khu vực để tăng cường đầu tư nhằm nâng cao chất lượng cuộc sống ở đây. Thành phố quyết định rằng các khu dân cư được nâng cấp sẽ nằm trong một hình chữ nhật con có kích thước (gồm hàng và cột), với và là các số lẻ. Lãnh đạo thành phố muốn chọn những nơi chất lượng sống còn thấp để ưu tiên cải tạo, nhưng họ cần đưa ra một tiêu chí đánh giá chung cho một vùng hình chữ nhật kích thước . Theo đó, "mức sống tiêu biểu" của một khu vực là trung vị của thứ hạng chất lượng cuộc sống của các khu dân cư bên trong đó. (xem phần dưới để biết định nghĩa về trung vị)
Khu vực được chọn để đầu tư phải có "mức sống tiêu biểu" lớn nhất (vì thứ hạng càng lớn thì chất lượng cuộc sống càng thấp) trong các khu vực có thể chọn. Bạn hãy giúp họ tìm ra "mức sống tiêu biểu" lớn nhất này nhé.
Giá trị trung vị của một dãy số (với là số lẻ) là giá trị thứ (ở vị trí chính giữa) của dãy số sau khi dãy đã được sắp xếp theo thứ tự tăng dần. Ví dụ, trung vị của dãy là (do dãy sau khi sắp xếp trở thành ; trung vị của dãy là (do dãy sau khi sắp xếp trở thành .
Dữ liệu vào:
Dòng đầu tiên chứa bốn số nguyên , , , , lần lượt là kích thước của thành phố Nồi Hạ và kích thước vùng được chọn để nâng cao chất lượng cuộc sống. Dữ liệu vào đảm bảo và là các số lẻ.
Trong dòng còn lại, dòng thứ chứa số nguyên , trong đó là thứ hạng chất lượng cuộc sống của khu . Dữ liệu vào đảm bảo số này là đôi một phân biệt.
Dữ liệu ra:
In ra một số nguyên duy nhất là "mức sống tiêu biểu" lớn nhất của một khu vực có dạng hình chữ nhật kích thước .
Trong ví dụ ở trên, lãnh đạo thành phố nên chọn hình chữ nhật kích thước ở góc trái dưới làm khu vực được nâng cấp. Thứ hạng của các khu dân cư bên trong khu vực này lần lựot là (được sắp xếp theo thứ tự tăng dần là ). Nhu vậy, ``mức sống tiêu biểu'' của khu vực này là .
Giới hạn:
Bộ test của bài được chia làm các subtask như sau:
Subtask ( số điểm):
Subtask ( số điểm khác): và
Subtask ( số điểm khác):
Subtask ( số điểm khác):
Subtask ( số điểm khác):
Subtask ( số điểm khác):
Subtask ( số điểm còn lại): Không có ràng buộc gì thêm.
