{"problem":{"name":"Pond","description":{"content":"The land of a park _AtCoder_ is an $N\\times N$ grid with east-west rows and north-south columns. The height of the square at the $i$\\-th row from the north and $j$\\-th column from the west is given as","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc203_d"},"statements":[{"statement_type":"Markdown","content":"The land of a park _AtCoder_ is an $N\\times N$ grid with east-west rows and north-south columns. The height of the square at the $i$\\-th row from the north and $j$\\-th column from the west is given as $A_{i,j}$.\nTakahashi, the manager, has decided to build a square pond occupying $K \\times K$ squares in this park.\nTo do this, he wants to choose a square section of $K \\times K$ squares completely within the park whose **median** of the heights of the squares is the lowest. Find the median of the heights of the squares in such a section.\nHere, the **median** of the heights of the squares in a $K \\times K$ section is the height of the $(\\left\\lfloor\\frac{K^2}{2}\\right\\rfloor +1)$\\-th highest square among the $K^2$ squares in the section, where $\\lfloor x\\rfloor$ is the greatest integer not exceeding $x$.\n\n## Constraints\n\n*   $1 \\leq K \\leq N \\leq 800$\n*   $0 \\leq A_{i,j} \\leq 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n$A_{1,1}$ $A_{1,2}$ $\\ldots$ $A_{1,N}$\n$A_{2,1}$ $A_{2,2}$ $\\ldots$ $A_{2,N}$\n$:$\n$A_{N,1}$ $A_{N,2}$ $\\ldots$ $A_{N,N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc203_d","tags":[],"sample_group":[["3 2\n1 7 0\n5 8 11\n10 4 2","4\n\nLet $(i,j)$ denote the square at the $i$\\-th row from the north and $j$\\-th column from the west. We have four candidates for the $2 \\times 2$ section occupied by the pond: ${(1,1),(1,2),(2,1),(2,2)}, {(1,2),(1,3),(2,2),(2,3)}, {(2,1),(2,2),(3,1),(3,2)}, {(2,2),(2,3),(3,2),(3,3)}$.  \nWhen $K=2$, since $\\left\\lfloor\\frac{2^2}{2}\\right\\rfloor+1=3$, the median of the heights of the squares in a section is the height of the $3$\\-rd highest square, which is $5$, $7$, $5$, $4$ for the candidates above, respectively. We should print the lowest of these: $4$."],["3 3\n1 2 3\n4 5 6\n7 8 9","5"]],"created_at":"2026-03-03 11:01:14"}}