VNOI Marathon 08

Một mặt bàn nằm ngang được chia làm lưới ô vuông, trong mỗi ô có ghi một số tự nhiên.

Cho 1 con xúc xắc nằm vừa vặn trên một ô của lưới. Mỗi mặt của xúc xắc là một số từ 1 đến 6. Ban đầu, mặt trước là số 1, mặt trên là số 2 và mặt bên phải là số 3, các mặt đối diện có tổng số là 7. Mỗi lần, con xúc xắc có thể lăn về phía trái, phải, trước, sau. Mỗi lần tiếp xúc với mặt bàn, ta mất một chi phí bằng số ghi trên ô mà xúc xắc đang nằm trên nhân với số trên mặt của xúc xắc đang tiếp xúc với mặt bàn.

Hãy tìm cách lăn từ một ô đến một ô khác trên mặt bàn để đạt chi phí nhỏ nhất.

Dữ liệu

• Dòng đầu ghi 2 số M, N lần lượt là số dòng và số cột của lưới ô trên mặt bàn.
• M dòng sau, mỗi dòng ghi N số nguyên không quá 100 là số ghi trên các ô lưới của mặt bàn. Các dòng được liệt kê theo thứ tự từ xa đến gần, các số trên mỗi dòng liệt kê từ trái sang phải.
• Dòng cuối ghi 2 cặp số lần lượt là tọa độ (dòng, cột) của ô bắt đầu và ô kết thúc.

Kết quả

Ghi ra một số duy nhất là chi phí nhỏ nhất tìm được.

Giới hạn

1 ≤ M,N ≤ 50.

Ví dụ

Dữ liệu
3 3
1 2 3
4 5 6
7 8 9
2 2 3 3

Kết quả
52