N from top to buttom, and columns are numbered from. M from left to right. The cell at the i-th row and the j-th column is denoted by. ), and the exit of the save is located at the cell. Each cell in this cave contains a number, which is called the magic value. The magic value of cell. When Bob moves from one cell to an unvisited cell, he gains energy points equals to the product of two magic values. It means, if Bob moves from cell. Bob can move between cells that share an edge . On the exit cell, Bob can choose not to exit the cave and continue to explore the cave if he want to. Can you help him find the maximum number of energy points he can gain when he exits the cave.
Bob is stuck in a cave represented by a matrix of mathbf{N} N rows and mathbf{M} M columns, where rows are numbered from mathbf{1} 1 to mathbf{N} N from top to buttom, and columns are numbered from mathbf{1} 1 to mathbf{M} M from left to right. The cell at the i-th row and the j-th column is denoted by {(i, j)} (i,j). Bob is currently at the cell (mathbf{S_R}, mathbf{S_C}) (S R ,S C ), and the exit of the save is located at the cell (mathbf{T_R}, mathbf{T_C}) (T R ,T C ). Each cell in this cave contains a number, which is called the magic value. The magic value of cell {(i, j)} (i,j) is mathbf{V_{ij}} V ij . When Bob moves from one cell to an unvisited cell, he gains energy points equals to the product of two magic values. It means, if Bob moves from cell {(i, j)} (i,j) to cell {(x, y)} (x,y), and cell (x, y) is unvisited, he will gain mathbf{V_{ij} times V_{xy}} V ij ×V xy energy points. Bob can move between cells that share an edge (not just a corner). On the exit cell, Bob can choose not to exit the cave and continue to explore the cave if he want to. Can you help him find the maximum number of energy points he can gain when he exits the cave.
