{"raw_statement":[{"iden":"statement","content":"Mixed Dimensions is an innovative company that is specialized in 3D printing technologies. They are planning to 3D print decorative tiles to be used in the beautiful pavements of Amman.\n\nAfter printing thousands of these decorative tiles, Mixed Dimensions washed the tiles with water to make them look fresh before they are delivered. Unfortunately, water gathered inside some places in the decorations. Observing the problem, they decided to fill any cavity (hole) in the decorations so that no water gathers after a rainy day.\n\nGiven a 3D printed tile that represents a grid of size R×C, and the height in unit cubes above each point in the grid, your task is to compute the volume of printing material needed to fill the cavities (holes).\n\nTwo units3 of printing material are needed to fill this tile.\n\nThe first line of input contains two integers R and C (1 ≤ R, C ≤ 500), the number of rows and columns of the base grid, respectively.\n\nEach of the following R lines contains C integers, each integer is between 1 and 109 and represents the height in unit cubes above one of the cells.\n\nPrint the volume of the printing material needed to fill the given tile so that no water gathers after a rainy day.\n\n"},{"iden":"input","content":"The first line of input contains two integers R and C (1 ≤ R, C ≤ 500), the number of rows and columns of the base grid, respectively.Each of the following R lines contains C integers, each integer is between 1 and 109 and represents the height in unit cubes above one of the cells."},{"iden":"output","content":"Print the volume of the printing material needed to fill the given tile so that no water gathers after a rainy day."},{"iden":"examples","content":"Input4 32 3 32 1 23 1 33 2 1Output2"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ R, C \\in \\mathbb{Z} $ be the dimensions of the grid, with $ 1 \\leq R, C \\leq 500 $.  \nLet $ H = (h_{i,j})_{R \\times C} $ be a matrix of integers, where $ h_{i,j} \\in [1, 10^9] $ represents the height of the grid cell at row $ i $, column $ j $.\n\n**Constraints**  \n1. $ 1 \\leq R, C \\leq 500 $  \n2. $ 1 \\leq h_{i,j} \\leq 10^9 $ for all $ i \\in \\{1, \\dots, R\\}, j \\in \\{1, \\dots, C\\} $\n\n**Objective**  \nCompute the total volume of material needed to fill all cavities such that no water can be retained after rainfall, assuming water flows to the boundary if possible. This is equivalent to computing the difference between the volume of the \"filled\" terrain (where every cell is filled up to the minimum height of the boundary path that connects it to the edge) and the original terrain.\n\nLet $ f(i,j) $ be the maximum water level that can be sustained at cell $ (i,j) $ without spilling to the boundary — i.e., the minimum of the maximum heights along all paths from $ (i,j) $ to the grid boundary. Then:\n\n$$\nf(i,j) = \\min_{\\text{path } P \\text{ from } (i,j) \\text{ to boundary}} \\left( \\max_{(x,y) \\in P} h_{x,y} \\right)\n$$\n\nThe volume of material needed is:\n\n$$\nV = \\sum_{i=1}^{R} \\sum_{j=1}^{C} \\max(0, f(i,j) - h_{i,j})\n$$","simple_statement":"You are given a grid of size R×C, where each cell has a height. Water can get trapped in holes between higher areas. Calculate the total volume of material needed to fill all holes so no water remains.","has_page_source":false}