Problem Description

A person named A, who is an employee of Indeed, is playing a game as follows:

There is a two-dimensional board consisting of $H \times W$ squares, with a height of $ H $ and a width of $ W $. The square located $x\ (1 \leq x \leq W)$ from the left and $y\ (1 \leq y \leq H)$ from the top is denoted as square $ (x, y) $.

Each square contains a non-negative integer, and the number written on square $ (x, y) $ is $ P_{(x, y)} $.

At any point, A is located on one of the squares on the board and acts according to the following rules:

• A can move to an adjacent square (up, down, left, or right), but cannot move outside the board.
• When visiting a square for the first time, A gains points equal to the number written on that square.
• When moving to a square that has not been visited yet, A gains a movement bonus equal to the product of the numbers written on the current square and the next square.
• No points are gained when moving to a square that has already been visited.

Initially, A visits the starting square $ (S_x, S_y) $. A wants to freely act according to the rules and eventually visit the goal square $ (G_x, G_y) $ to end the game. Note that A may return to the goal square after reaching it without ending the game.

Output the maximum total score A can achieve by acting according to the rules.

Input Format

The input is given from the standard input in the following format:

\[Important\] Previously, the input format was incorrectly described as $ P(y,x) $ instead of $ P(x,y) $. The description has been corrected. We apologize for the inconvenience (16:01).

$ H $ $ W $ $ S_x $ $ S_y $ $ G_x $ $ G_y $ $ P_{(1,1)} $ $ P_{(2,1)} $ … $ P_{(W,1)} $ $ P_{(1,2)} $ $ P_{(2,2)} $ … $ P_{(W,2)} $ : $ P_{(1,H)} $ $ P_{(2,H)} $ … $ P_{(W,H)} $

• The first line contains two integers $H, W\ (1 \leq H, W \leq 100)$ representing the height and width of the board, separated by spaces.
• The second line contains two integers $S_x, S_y\ (1 \leq S_x \leq W, 1 \leq S_y \leq H)$ representing the coordinates of the starting square, separated by spaces.
• The third line contains two integers $G_x, G_y\ (1 \leq G_x \leq W, 1 \leq G_y \leq H)$ representing the coordinates of the goal square, separated by spaces.
• The next $ H $ lines contain the information about the numbers written on each square. The $i(1 \leq i \leq H)$th line contains $ W $ integers $ P_{(1,i)} $, $ P_{(2,i)} $, …, $ P_{(W,i)} $ separated by spaces, representing the numbers written on squares $ (1,i) $, $ (2,i) $, …, $ (W,i) $.
• For any $x, y(1 \leq x \leq W, 1 \leq y \leq H)$, $0 \leq P_{(x,y)} \leq 100$.

Output Format

Output one line containing the maximum total score A can achieve by acting according to the rules. End the output with a newline.

Sample Input and Output

Sample Input #1

1 6
2 1
2 1
0 1 2 3 4 0

Sample Output #1

30

Sample Input #2

3 3
1 1
3 3
2 2 2
1 2 1
1 1 1

Sample Output #2

33

Sample Input #3

10 10
5 2
6 2
31 0 60 19 87 98 35 68 21 41
21 46 85 72 51 13 0 49 19 25
79 82 46 65 30 99 29 44 99 8
39 48 70 99 82 32 25 49 32 54
81 20 57 70 5 40 88 97 56 17
69 54 35 98 7 38 59 91 80 34
28 13 14 28 60 26 82 10 17 100
29 0 27 43 45 88 88 92 21 67
62 33 35 22 26 68 74 95 86 79
68 18 83 72 85 21 72 34 57 77

Sample Output #3

370423

Notes/Hints

Sample Explanation 1

Both the starting and goal squares are the second square from the left on the board. The maximum score that can be obtained on this board is 30 points, and an example of achieving this score is as follows:

• Visit the starting square $ (2,1) $. The number written on this square is 1. The total score at this point is 1 point.
• Visit square $ (3,1) $. The number written on this square is 2, and the movement bonus is $1 \times 2$ points. Therefore, the total score at this point is 5 points.
• Visit square $ (4,1) $. The number written on this square is 3, and the movement bonus is $2 \times 3$ points. Therefore, the total score at this point is 14 points.
• Visit square $ (5,1) $. The total score at this point is 30 points.
• Visit square $ (4,1) $. No change in score since it's a move between already visited squares.
• Visit square $ (3,1) $. No change in score.
• Visit square $ (2,1) $ and end the game. No change in score. The final total score is 30 points.

见题面 Input 部分

见题面 Output 部分