Dungeon

Cheolsu and Yeonghee are trapped in a dungeon represented by an \(N \times N\) grid. Cheolsu starts from the top-left corner \((0, 0)\) and must reach the bottom-right corner \((N-1, N-1)\) by moving only right (→) or down (↓). Meanwhile, Yeonghee starts from the top-right corner \((0, N-1)\) and must reach the bottom-left corner \((N-1, 0)\) by moving only left (←) or down (↓).

Every cell \((i, j)\) contains an integer value \(V[i][j]\) which may be positive, zero, or negative. As they traverse the dungeon, each player collects the items (cell values) from the cells they visit. If both players visit the same cell, the cell's value is counted only once.

Your task is to implement the function max_item_sum that returns the maximum total value that can be collected by both players combined.

A hint for a dynamic programming approach: Synchronize the moves by considering that both players take a total of \(2N-2\) moves. Let the step index be \(k\) (with \(0 \le k \le 2N-2\)). At step \(k\), if Cheolsu is at \((r_1, c_1)\) then \(c_1 = k - r_1\); similarly, if Yeonghee is at \((r_2, c_2)\) then \(c_2 = N-1 - (k - r_2)\). Define a state \(\text{dp}[k][r_1][r_2]\) as the maximum sum collected until step \(k\), and update the state by exploring the two possible moves for each player. When both players land on the same cell, add \(V[i][j]\) only once.

Be sure that your solution does not perform any input/output operations.

inputFormat

The function is provided a 2D integer array \(V\) of size \(N \times N\), where \(V[i][j]\) represents the value in cell \((i, j)\) of the dungeon.

outputFormat

The function should return an integer reflecting the maximum possible total value that can be collected by Cheolsu and Yeonghee combined.

sample

[[1,-1],[2,3]]

5