Dice Rolling Maximum Score

There is an n × m board where the cell in the i-th row and j-th column contains an integer a_i-1,j-1. A dice with 6 faces is placed at the top‐left cell (i.e. cell (0, 0)). The six faces of the dice are given in order: front, back, left, right, top, and bottom, with the corresponding values w₀, w₁, w₂, w₃, w₄, and w₅.

You need to roll the dice to cell (n-1, m-1) (i.e. the bottom‐right cell) using only two types of moves:

• Roll to the right: you move the dice one cell to the right (i.e. next column) using a horizontal roll.
• Roll downward: you move the dice one cell down (i.e. next row) using a vertical roll.

When the dice is rolled, its faces change according to the following rules:

• Rolling to the right: if the current dice state is represented by the tuple (f, b, l, r, t, d) (where f = front, b = back, l = left, r = right, t = top, d = bottom), then after a roll to the right the new state becomes:

\[ (f,\;b,\;l,\;r,\;t,\;d) \xrightarrow{\text{right}} (f,\;b,\;d,\;t,\;l,\;r). \]

• Rolling downward: if the current dice state is (f, b, l, r, t, d), then after a roll downward the new state becomes:

\[ (f,\;b,\;l,\;r,\;t,\;d) \xrightarrow{\text{down}} (d,\;t,\;l,\;r,\;f,\;b). \]

At every moment (including the starting and ending positions), you add to your score the product of the number written on the bottom face of the dice and the number written on the board cell where the dice rests. Your goal is to maximize the total score accumulated along a valid path from (0, 0) to (n-1, m-1).

Input Format: The first line contains two integers n and m. Then follow n lines each containing m integers describing the board. The last line contains 6 integers: w₀, w₁, w₂, w₃, w₄, w₅, representing the dice values in the order front, back, left, right, top, bottom.

Output Format: Output a single integer, which is the maximum total score you can achieve.

inputFormat

The input contains:

1. The first line contains two integers n and m.
2. The next n lines each contain m integers representing the board, where the j-th number of the i-th line is a_i-1,j-1.
3. The last line contains 6 integers: w₀, w₁, w₂, w₃, w₄, w₅.

It is guaranteed that all numbers are separated by spaces.

outputFormat

Output a single integer representing the maximum total score achievable.

sample

2 2
1 2
3 4
1 2 3 4 5 6

28