{"problem":{"name":"Stamp Game","description":{"content":"There is a grid with $H$ horizontal rows and $W$ vertical columns. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left.   For each pair of integers $(i, j)$","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc228_f"},"statements":[{"statement_type":"Markdown","content":"There is a grid with $H$ horizontal rows and $W$ vertical columns. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left.  \nFor each pair of integers $(i, j)$ such that $1 \\leq i \\leq H$ and $1 \\leq j \\leq W$, $(i, j)$ contains a positive integer $A_{i,j}$. Additionally, every square is painted white.\nTakahashi has a rectangular black stamp that can cover $h_1$ rows and $w_1$ columns, and Aoki has a rectangular white stamp that can cover $h_2$ rows and $w_2$ columns. Using these stamps and the grid, they will play a game against each other.\nFirst, Takahashi presses his black stamp to paint a rectangular region with $h_1$ rows and $w_1$ columns black.  \nThat is, he chooses a pair of integers $(i, j)$ such that $1 \\leq i \\leq H - h_1 + 1$ and $1 \\leq j \\leq W - w_1 + 1$, and paints black every square $(r, c)$ such that $i \\leq r \\leq i + h_1 - 1$ and $j \\leq c \\leq j + w_1 - 1$.\nSecond, Aoki presses his white stamp to paint a rectangular region with $h_2$ rows and $w_2$ columns white.  \nThat is, he chooses a pair of integers $(i, j)$ such that $1 \\leq i \\leq H - h_2 + 1$ and $1 \\leq j \\leq W - w_2 + 1$, and paints white every square $(r, c)$ such that $i \\leq r \\leq i + h_2 - 1$ and $j \\leq c \\leq j + w_2 - 1$.  \nIf some of these squares are already painted black by Takahashi, they will also become white.\nThe game's score is defined as the sum of the integers written on the squares painted black after Takahashi and Aoki press their stamps as described above. Takahashi follows the optimal strategy to make the score as large as possible, while Aoki follows the optimal strategy to make the score as small as possible. What will the game's score be?\n\n## Constraints\n\n*   $2 \\leq H, W \\leq 1000$\n*   $1 \\leq h_1, h_2 \\leq H$\n*   $1 \\leq w_1, w_2 \\leq W$\n*   $1 \\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$H$ $W$ $h_1$ $w_1$ $h_2$ $w_2$\n$A_{1, 1}$ $A_{1, 2}$ $\\cdots$ $A_{1, W}$\n$A_{2, 1}$ $A_{2, 2}$ $\\cdots$ $A_{2, W}$\n$\\vdots$\n$A_{H, 1}$ $A_{H, 2}$ $\\cdots$ $A_{H, W}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc228_f","tags":[],"sample_group":[["3 4 2 3 3 1\n3 1 4 1\n5 9 2 6\n5 3 5 8","19\n\nThe game will go as follows.\n\n*   Initially, all squares are painted white.\n*   First, Takahashi presses his $2 \\times 3$ black stamp to paint the following six squares black: $(2, 2), (2, 3), (2 ,4), (3, 2), (3, 3), (3, 4)$.\n*   Second, Aoki presses his $3 \\times 1$ white stamp to paint the following three squares white: $(1, 4), (2, 4), (3, 4)$.\n*   Eventually, the following four squares are painted black: $(2, 2), (2, 3), (3, 2), (3, 3)$, for a score of $9 + 2 + 3 + 5 = 19$."],["3 4 2 3 3 4\n3 1 4 1\n5 9 2 6\n5 3 5 8","0\n\nAfter Aoki presses his stamp, all squares will be white, for a score of $0$."],["10 10 3 7 2 3\n9 7 19 7 10 4 13 9 4 8\n10 15 16 3 18 19 17 12 13 2\n12 18 4 9 13 13 6 13 5 2\n16 12 2 14 18 17 14 7 8 12\n12 13 17 12 14 15 19 7 13 15\n5 2 16 10 4 6 1 2 7 8\n10 14 14 10 9 13 11 4 9 19\n16 12 3 19 19 6 2 19 14 20\n15 3 19 19 2 10 1 4 3 15\n13 20 5 6 19 1 7 17 10 19","180"]],"created_at":"2026-03-03 11:01:14"}}