Roger Cube Game

In the Roger Cube Game there is a board of size (n \times m) and a cube called Roger. The board is divided into cells; each cell contains an integer which is either (-1) (forbidden cell) or an integer between (0) and (255) (inclusive). Roger is a cube with six faces. Each face has an integer between (1) and (6).

We initially place Roger on a specified cell of the board. Then Roger rolls from cell to cell. Every time Roger enters a new cell (the starting cell does not count), the cost incurred is calculated by multiplying the number on the top face of the cube by the number written on that cell; the total travel cost is the sum of these products. Roger is not allowed to enter any cell containing (-1) (this immediately ends the game).

Some faces of Roger may have their numbers predetermined at the start, while for others the number is unknown (represented by (-1)). For any face with an unknown number, you are free to assign any integer in the legal range provided that the assignment is consistent throughout the journey. In fact, if a face is not forced to show a particular number at the destination, you may choose the smallest legal number (1) to minimize the cost. Additionally, at the destination cell, there may be constraints requiring that some of the visible faces (top, bottom, front, back, left, right) show specified numbers. If a face is predetermined the value must match; if it is unknown, you must choose its value to satisfy the requirement.

There are two tasks in this problem:

Task One: Roger is allowed to roll only to the right or forward. In our formulation the allowed moves from any cell are: right (i.e. column +1) and down (i.e. row +1).

Task Two: Roger can roll in all four directions (up, down, left, right).

The cube rolls in the following way. Let the state of the cube be represented by a tuple ((T, B, F, Ba, L, R)) which indicates the physical face in the top, bottom, front, back, left and right positions respectively. The rolling operations change the configuration as follows:

• Roll Down (move down): [ (T, B, F, Ba, L, R) \to (F, Ba, B, T, L, R) ]

• Roll Right (move right): [ (T, B, F, Ba, L, R) \to (L, R, F, Ba, B, T) ]

• Roll Up (move up): [ (T, B, F, Ba, L, R) \to (Ba, F, T, B, L, R) ]

• Roll Left (move left): [ (T, B, F, Ba, L, R) \to (R, L, F, Ba, T, B) ]

When moving to a new cell whose board value is (v) and the top face (after rolling) belongs to physical face (f) (with assigned value (a_f)), the cost incurred in that move is (a_f \times v). The starting cell does not add any cost.

Your task is to compute the minimum travel cost from the starting cell to the destination cell following the allowed moves (depending on the task) and obeying the following conditions:

1. Roger must never enter a cell with value (-1).
2. The initial cube configuration is given as six numbers in the order: top, bottom, front, back, left, right. For any face whose initial value is (-1) you may assign any value in ([1,6]).
3. At the destination, the cube’s configuration (again given in the order top, bottom, front, back, left, right) must satisfy the final requirements. For each position, if the final required number is not (-1), then the value on that face (i.e. the assigned value of the corresponding physical face) must equal the required number.

If no valid path exists that satisfies the constraints, output (-1). Otherwise, output the minimum travel cost.

Note: For unknown faces, to minimize cost you should choose (1) unless a final requirement forces a different value on the corresponding face that ends up in that position at the destination.

inputFormat

The input is given as follows:

• The first line contains an integer (t) (either 1 or 2) indicating the task type. If (t = 1) then Roger can move only down and right; if (t = 2) then Roger can move in all four directions.
• The second line contains two integers (n) and (m) ((1 \le n, m \le) small constraints) representing the number of rows and columns of the board.
• The third line contains two integers (r_s) and (c_s) denoting the starting cell (0-indexed).
• The fourth line contains two integers (r_d) and (c_d) denoting the destination cell (0-indexed).
• The next (n) lines each contain (m) integers. Each integer is either (-1) or an integer between (0) and (255); these represent the board.
• The next line contains 6 integers representing the initial cube configuration in the order: top, bottom, front, back, left, right. A value of (-1) means the face is unknown.
• The final line contains 6 integers representing the final required configuration in the same order. A value of (-1) means there is no requirement for that face at the destination.

outputFormat

Output a single integer which is the minimum travel cost from the starting cell to the destination cell satisfying all constraints. If there is no valid path, output (-1).

sample

1
2 2
0 0
1 1
2 3
4 5
-1 2 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1

8