Trong một cuộc thi Robocon người ta tổ chức phần thi “leo cột” – phần thi thể hiện tốc độ tư duy và kỹ năng, kỹ xảo của các chú Robot. Một sa bàn kích thước \(m \times n\) \((0 < m,n\ < 101)\) được chia thành các lưới ô vuông đơn vị với kích thước \(1 \times 1\) gắn với trục tọa độ OXY như hình 1. Kích thước \(m\) tính theo đơn vị trục OX.

Hình 1	Hình 2

Trên các ô vuông người ta xây các cột hình khối chữ nhật có mặt cắt \(1 \times 1\) và chiều cao là một số nguyên dương không vượt quá 100, các cột có chiều cao bằng nhau mà sát nhau thì sẽ tạo thành một mặt phẳng.

Khi đến phần thi của mình, Robot được đặt vào một ô vuông tọa độ \((x_{1},y_{1})\) – đó có thể là bề mặt sa bàn hoặc đỉnh của một cột nào đó. Tại một vị trí \((x_{2},y_{2})\) khác người ta đặt một thiết bị phát sóng, Robot có khả năng bắt sóng và tính ra được vị trí đặt thiết bị này. Từ vị trí \((x_{1},y_{1})\) hiện tại Robot phải đi đến vị trí \((x_{2},y_{2})\), có thể phải leo lên hay leo xuống các cột trên sa bàn và Robot phải tìm đường đi tốn ít năng lượng nhất. Mỗi bước đi của Robot luôn bắt đầu từ một ô vuông đến một ô vuông khác có chung một cạnh theo một trong bốn quy tắc sau:

(1) Hai ô vuông thuộc cùng một mặt phẳng ngang (song song với mặt đất) có năng lượng tiêu hao là 1.

(2) Hai ô vuông thuộc cùng một mặt phẳng đứng (vuông góc với mặt đất) có năng lượng tiêu hao là 2.

(3) Hai ô vuông không thuộc cùng một mặt phẳng (vuông góc với nhau) có năng lượng tiêu hao là 2.

(4) Từ ô kề đỉnh của cột lên đỉnh của cột có năng lượng tiêu hao là 1.

Yêu cầu: Bạn hãy tìm đường đi cho Robot với mức tiêu hao năng lượng nhỏ nhất.

Dữ liệu vào:

+ Dòng đầu tiên ghi 2 số nguyên \(m,\ n\) cách nhau một khoảng trắng.

+ \(m\) dòng tiếp theo, mỗi dòng ghi \(n\) số, các số cách nhau một khoảng trắng. Số thứ \(j\) trên dòng \(i\) thể hiện độ cao của cột tại tọa độ \((i,j)\) trên sa bàn. Độ cao bằng 0 thể hiện rằng không có cột nào tại vị trí đó.

+ Dòng cuối cùng ghi 4 số \(x_{1},\ y_{1},\ x_{2},\ y_{2}\), các số cách nhau một khoảng trắng.

Kết quả:

+ Ghi một số nguyên dương là năng lượng tối thiểu mà robot đã sử dụng.

Ví dụ:

Giới hạn:

+ Có 30% số test ứng với 30% số điểm của bài có \(0 \leq m,n \leq 30\)

+ Có 30% số test ứng với 30% số điểm của bài có \(0 \leq m,n \leq 60\)

+ Có 40% số test ứng với 40% số điểm của bài có \(0 \leq m,n \leq 100\)