플래티넘 VA city is an \(R \times C\) grid; the cell in row \(i\), column \(j\) holds a distinct quality rank — the numbers \(1 \dots R\cdot C\) each appear exactly once. A residential block is any \(H \times W\) axis-aligned rectangle of cells (\(H\cdot W\) is odd). The quality of a block is the median of the \(H\cdot W\) ranks inside it.
Over all possible placements of an \(H \times W\) block, output the minimum achievable quality (median).
Note. This is an adaptation of an IOI function-implementation task to an interactive stdin/stdout problem. The test data is RiseOJ-generated (self-validated against an independent brute force), not the official IOI data.
Interaction / I/O protocol
Input. Line 1: \(R\), \(C\), \(H\), \(W\). The next \(R\) lines each contain \(C\) integers — the grid (a permutation of \(1 \dots R\cdot C\)).
Output. Print one integer: the minimum block median.
Example. Grid (R=4,C=3,H=W=3):
5 11 12
16 1 30
2 6 15
10 18 25
The two 3×3 blocks have medians 11 and 15; the answer is 11.
- \(1 \le H \le R \le 500\), \(\; 1 \le W \le C \le 500\)
- \(H \cdot W\) is odd
- The grid is a permutation of \(1 \dots R\cdot C\)
Line 1: \(R\), \(C\), \(H\), \(W\). The next \(R\) lines each contain \(C\) integers — the grid (a permutation of \(1 \dots R\cdot C\)).
Print one integer: the minimum block median.