Một con sông có kích thước ~ m×n ~. Mỗi ô vuông đơn vị trên sông có một độ cao, mỗi một độ cao là một số nguyên dương ≤1000. Một người muốn đi từ đầu bờ bên này (hàng trên cùng) sang cuối bờ bên kia (hàng dưới cùng). Người đó chỉ có thể đi từ ô đang đứng tới một ô mới theo hướng thẳng đứng, chéo trái, hoặc chéo phải. Giả thiết rằng người đó không vượt ra hai mép trái và phải của con sông.

Hãy tìm đường đi sao cho người đó phải vượt qua sông với quãng đường ngắn nhất. Mỗi lần đi từ một ô sang ô mới tiếp theo người đó phải đi hết quãng đường bằng độ chênh lệnh cao (bằng trị tuyệt đối hiệu giá trị của 2 ô đó).

Dữ liệu vào:

• Dòng đầu tiên: Chứa 2 số ~ m, n (1≤m,n≤1000) ~
• Trong ~ m ~ dòng tiếp theo ghi ~ n ~ số nguyên dương trong bảng ~ m×n ~.

Kết quả:

• Ghi duy nhất một số nguyên dương là quãng đường ngắn nhất tìm được.

Input

5 5
3   3  8  1  5
8   7  3 14  1
6   7 18  1  1
20 20 17 23 24
31 20 27 10  6 

Output

12 

Ràng buộc:

• Có 30% số test tương ứng ~ 1≤m,n≤100 ~
• Có 70% số test khác tương ứng ~ 100<m,n≤1000 ~