{"raw_statement":[{"iden":"statement","content":"After another great year for UFPE's competitive programming team, the coach Ivan decided to gift the team and invest in building a pool at an area nearby. After reuniting with the group to arrange the details, four things were decided:\n\nThere was only one limitation stopping us from always digging deeper: Rocks. Because of rocks underground, it wouldn't be possible to dig more than a certain depth in each part of the area.\n\nTo help us pick the best place for the pool, we split the area in cells, measured how deep we could dig in each of them and mapped it into a grid, such as the one shown below: \n\nTo help us estimate the costs of the building, you must calculate the maximum possible depth of the pool.\n\nS, N and M, the size of the pool and the dimensions of the terrain. Followed by N lines with M integers on each, the depth of each cell on the area.\n\n$1 <= N$, $M <= 10^6$, $S <= N dot.op M <= 10^6$, $1 <=$ Depths $<= 10^8$\n\nD, the maximum depth of the pool.\n\nIn the case presented on the statement, for a pool of size 1, we could choose one of the 9 units deep cells to have a 9 units deep pool.\n\nFor a pool of size 2 however, the deepest it could be is 8 units, by choosing both cells with 8 units deep. Because the 9 units deep cells aren't connected and combining one of them with a 7 units deep cell would make the entire pool 7 units deep.\n\nFor all other sizes, you must use at least one 7 deep cell to keep the pool connected, so the pool would be 7 units deep.\n\n"},{"iden":"input","content":"S, N and M, the size of the pool and the dimensions of the terrain. Followed by N lines with M integers on each, the depth of each cell on the area.$1 <= N$, $M <= 10^6$, $S <= N dot.op M <= 10^6$, $1 <=$ Depths $<= 10^8$"},{"iden":"output","content":"D, the maximum depth of the pool."},{"iden":"examples","content":"Input1 2 4\n9 7 7 9\n7 8 8 7\nOutput9Input2 2 4\n9 7 7 9\n7 8 8 7\nOutput8Input3 2 4\n9 7 7 9\n7 8 8 7\nOutput7"},{"iden":"note","content":"In the case presented on the statement, for a pool of size 1, we could choose one of the 9 units deep cells to have a 9 units deep pool.For a pool of size 2 however, the deepest it could be is 8 units, by choosing both cells with 8 units deep. Because the 9 units deep cells aren't connected and combining one of them with a 7 units deep cell would make the entire pool 7 units deep.For all other sizes, you must use at least one 7 deep cell to keep the pool connected, so the pool would be 7 units deep."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, M, S \\in \\mathbb{Z}^+ $ denote the dimensions of the grid and the required pool area (number of cells).  \nLet $ G = (g_{i,j})_{N \\times M} $ be a grid of non-negative integers, where $ g_{i,j} $ is the maximum diggable depth at cell $ (i,j) $.  \n\n**Constraints**  \n1. $ 1 \\leq N, M \\leq 10^6 $  \n2. $ 1 \\leq S \\leq N \\cdot M \\leq 10^6 $  \n3. $ 1 \\leq g_{i,j} \\leq 10^8 $ for all $ i \\in \\{1, \\dots, N\\}, j \\in \\{1, \\dots, M\\} $  \n\n**Objective**  \nFind the maximum value $ D \\in \\mathbb{Z}^+ $ such that there exists a connected region $ R \\subseteq \\{1, \\dots, N\\} \\times \\{1, \\dots, M\\} $ with $ |R| = S $ and  \n$$\nD = \\min_{(i,j) \\in R} g_{i,j}\n$$  \nwhere connectivity is defined as 4-directional adjacency (up, down, left, right).","simple_statement":"Given a grid of size N×M, each cell has a digging depth. Find the maximum possible depth of a rectangular pool of exactly S connected cells, where the pool's depth is limited by the shallowest cell in it.","has_page_source":false}