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 một 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ừ đến . Ban đầu, mặt trước là số , mặt trên là số và mặt bên phải là số , các mặt đối diện có tổng số là . 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 vào:
Dòng đầu ghi hai số lần lượt là số dòng và số cột của lưới ô trên mặt bàn;
dòng sau, mỗi dòng ghi số nguyên dương không quá 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 hai cặp số lần lượt là tọa độ (dòng, cột) của ô bắt đầu và ô kết thúc.
Dữ liệu ra:
Ghi ra một số duy nhất là chi phí nhỏ nhất tìm được.