{"raw_statement":[{"iden":"statement","content":"Michael and Trevor have just pulled off the biggest heist Los Santos has ever seen! However, they must now escape the cops. In order to evade quickly, they decide to split up and drive dirt bikes across the map. The map is a hilly terrain laid out as a grid. Michael is traveling from the top row of the map to the bottom row, while Trevor is driving from the leftmost column to the rightmost column.\n\nEvery minute Michael must move downwards and Trevor must move rightwards. Specifically, Michael can move from position $(i, j)$ at time $t$ to either $(i + 1, j -1)$, $(i + 1, j)$ or $(i + 1, j + 1)$ at time $t + 1$. Trevor can move from position $(i, j)$ at time $t$ to $(i -1, j + 1)$, $(i, j + 1)$ or $(i + 1, j + 1)$ at time $t + 1$\n\nTo further confuse the cops and help them escape, they decide to meet somewhere along the way and swap vehicles quickly. This means that they must be in the same position at the same time at least once.\n\nBoth love pulling off stunts, and for each hill that they drive over, they will get points equal to the height of that hill. Help them maximize their total style points from this journey!\n\nThe first line contains 2 space-separated integers $n$ (the number of rows) and $m$ (the number of columns). The following $n$ lines contain $m$ integers each, denoting the heights of each hill in the grid.\n\n$1 <= n <= 10^3$\n\n$1 <= m <= 10^3$\n\n$1 <= h e i g h t (i, j) <= 10^5$\n\nA single integer, the maximum style points that can be obtained by the pair.\n\nIf the starting position is the same, this counts as a 'meeting' and they need not meet again. Also, if they drive over the same hill they both get style points from that hill.\n\n"},{"iden":"input","content":"The first line contains 2 space-separated integers $n$ (the number of rows) and $m$ (the number of columns). The following $n$ lines contain $m$ integers each, denoting the heights of each hill in the grid.$1 <= n <= 10^3$$1 <= m <= 10^3$$1 <= h e i g h t (i, j) <= 10^5$"},{"iden":"output","content":"A single integer, the maximum style points that can be obtained by the pair."},{"iden":"examples","content":"Input2 2\n1 1\n2 2\nOutput7\nInput3 3\n1 2 3\n4 5 6\n7 8 9\nOutput42\n"},{"iden":"note","content":"If the starting position is the same, this counts as a 'meeting' and they need not meet again. Also, if they drive over the same hill they both get style points from that hill."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of rows and columns of the grid.  \nLet $ H = (h_{i,j})_{1 \\le i \\le n, 1 \\le j \\le m} $ be the height matrix, where $ h_{i,j} \\in \\mathbb{Z}^+ $ is the height at position $ (i,j) $.  \n\nMichael starts at some position $ (1, j_M) $ with $ 1 \\le j_M \\le m $, and moves from $ (i, j) $ to $ (i+1, j') $ where $ j' \\in \\{j-1, j, j+1\\} $, until reaching row $ n $.  \nTrevor starts at some position $ (i_T, 1) $ with $ 1 \\le i_T \\le n $, and moves from $ (i, j) $ to $ (i', j+1) $ where $ i' \\in \\{i-1, i, i+1\\} $, until reaching column $ m $.  \n\nThey must meet at least once at some position $ (i, j) $ at the same time step $ t $, meaning:  \n- Michael reaches $ (i, j) $ at step $ i - 1 $ (since he moves down $ i-1 $ times from row 1),  \n- Trevor reaches $ (i, j) $ at step $ j - 1 $ (since he moves right $ j-1 $ times from column 1),  \n- Thus, $ i - 1 = j - 1 \\Rightarrow i = j $.  \n\nSo they can only meet on the diagonal $ i = j $.  \n\n**Constraints**  \n1. $ 1 \\le n, m \\le 10^3 $  \n2. $ 1 \\le h_{i,j} \\le 10^5 $  \n3. Michael’s path: $ (1, j_0) \\to (2, j_1) \\to \\dots \\to (n, j_{n-1}) $, with $ |j_{k} - j_{k-1}| \\le 1 $  \n4. Trevor’s path: $ (i_0, 1) \\to (i_1, 2) \\to \\dots \\to (i_{m-1}, m) $, with $ |i_{k} - i_{k-1}| \\le 1 $  \n5. There exists $ k \\in \\{1, \\dots, \\min(n,m)\\} $ such that $ j_{k-1} = i_{k-1} = k $ (i.e., they meet at $ (k,k) $)  \n\n**Objective**  \nMaximize the total style points:  \n$$\n\\max_{\\substack{\\text{Michael's path } P_M \\\\ \\text{Trevor's path } P_T \\\\ \\text{with } \\exists k: P_M(k) = P_T(k) = (k,k)}} \\left( \\sum_{(i,j) \\in P_M} h_{i,j} + \\sum_{(i,j) \\in P_T} h_{i,j} \\right)\n$$  \nNote: If $ (k,k) $ is visited by both, $ h_{k,k} $ is counted twice.","simple_statement":"Michael and Trevor start driving on a grid. Michael begins at the top row and moves down to the bottom row. Trevor begins at the leftmost column and moves right to the rightmost column. Each minute, both must move: Michael goes down one row (and can shift left, stay, or right), Trevor goes right one column (and can shift up, stay, or down). They must meet at least once at the same cell at the same time. Every time they drive over a hill, they earn points equal to its height. If they both drive over the same hill (including when they meet), both get the points. Find the maximum total style points they can earn.","has_page_source":false}