Background

Tengyuu Chiyo once said: “Ability cards will eventually follow the trend and become stale, and the market will eventually return to everyday life. This is the law of development.” But for some reason, contrary to what the gods said, the value of the cards was speculated. Is someone speculating the cards’ value? Of course. Or rather, are there scalpers hoarding these cards? When the card market order fell completely into chaos, a market that even the gods could not interfere with appeared.

$$\quad\tag*{\small\textit{---TH18.5 恋弹者们的黑集市}}$$

Marisa is investigating the highlands of Youkai Mountain to collect ability cards scattered across various places. At this time, she encounters Komakusa Sannyo, who lives here.

Komakusa Sannyo, who can handle things smoothly between the kappa and the tengu, controls a large amount of resources here. Obviously, she also has a large number of ability cards—exactly Marisa’s target.

“Want these cards? Then let’s play a game.”

“If you win, all these cards are yours; if you lose, you must hand over all the cards you have.”

Problem Description

Original Statement

Komakusa Sannyo places a die with weights written on all six faces onto a board. The board is filled with many colorful numbers. The cell in row $i$ and column $j$ contains the number $a_{i-1,j-1}$.

“Whether you can get these ability cards depends on your score.”

Marisa has two ways to move this die: roll it to the next column, or roll it to the next row. Note that after rolling the die, the numbers on its faces change as it tumbles. Now Marisa needs to roll the die to row $n$ and column $m$.

Marisa’s score is defined as follows: at all times, take the number on the face of the die that is in contact with the board, multiply it by the number on the board at that position, and sum these products over the whole process. Only if Marisa maximizes this sum can she obtain the cards she needs.

Can you help Marisa?

Simplified Statement

There is an $n\times m$ board. The cell in row $i$ and column $j$ contains the number $a_{i-1,j-1}$.

Now there is a die. Its six faces, in the order front, back, left, right, top, bottom, contain the numbers $w_0,w_1,w_2,w_3,w_4,w_5$. The die is initially placed at position $(0,0)$, and you need to roll it to $(n-1,m-1)$.

The die can be rolled in only two ways: roll to the next row, or roll to the next column. We define the weight of a path as the sum, over the entire process (including when the die is at the start and the end), of the product of the number written on the bottom face of the die and the number written in the cell where the die currently is.

(For easier reading, the numbers on the die have been hidden.)

Now you need to maximize this sum of products.

Input Format

• The first line contains two positive integers $n, m$, indicating the size of the board.
• The next $n$ lines each contain $m$ values describing the board elements $a_{i,j}$.
• The next line contains six integers, representing $w_0,w_1,w_2,w_3,w_4,w_5$.

Output Format

• Output one integer in a single line, indicating the maximum weight that can be obtained.

5 5
2 8 15 1 10
5 19 19 3 5
6 6 2 8 2
12 16 3 8 17
12 5 3 14 13
1 1 1 1 1 1

97

2 5
2 8 15 3 10
5 19 19 3 5
1 2 3 4 5 6

194

Hint

Sample Explanation

Sample 1 Explanation

One optimal path is $(0,0)\to(0,1)\to(1,1)\to(1,2)\to(1,3)\to(2,3)\to(3,3)\to(3,4)\to(4,4)$.

The total weight is $2+8+19+19+3+8+8+17+13=97$.

Sample 2 Explanation

One optimal path is $(0,0)\to(0,1)\to(1,1)\to(1,2)\to(1,3)\to(1,4)$.

Constraints and Notes

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n,m\le} & \textbf{Special Property} & \textbf{Score} \\\hline 1 & 10 & - & 10 \\\hline 2 & 100 & - & 30 \\\hline 3 & 10^3 & \textbf{A} & 10 \\\hline 4 & 10^3 & - & 50 \\\hline \end{array}$$

• Special Property $\textbf{A}$: it is guaranteed that $w_i=1,i=0,1,2,\cdots 5$.

For all testdata, it is guaranteed that $1\le n,m\le 10^3$, $|a_i|\le 10^3$, and $|w_i|\le 10^3$.

Translated by ChatGPT 5