P2004 Territory Selection

As a leader who commands countless troops in a virtual world, Xiao Z believes that timing, terrain, and unity among people are all indispensable. Therefore, carefully choosing the location of the capital is very important to Xiao Z. The capital is considered to be a square occupying $C \times C$. Xiao Z wants you to find a suitable position such that the sum of land values covered by the capital is maximized.

The first line contains three integers $N, M, C$, denoting the height and width of the map and the side length of the capital. The next $N$ lines each contain $M$ integers, giving the value of each plot on the map. Values may be negative.

One line with two integers $X, Y$, denoting the coordinates of the top-left corner of the capital. It is guaranteed that the optimal solution is unique.

For $60\%$ of the testdata, $N, M \le 50$. For $90\%$ of the testdata, $N, M \le 300$. For $100\%$ of the testdata, $1 \le N, M \le 10^3$, $1 \le C \le \min(N, M)$. The absolute value of each tile's value does not exceed $32767$. Translated by ChatGPT 5