Trong một chuyến thám hiểm thung lũng số nguyên trên hành tinh Cyber-CBRT, robot thám hiểm p2o2HuaGiaBao cần di chuyển từ trạm chỉ huy tại góc trên cùng bên trái đến trạm truyền tin tại góc dưới cùng bên phải của một bản đồ địa hình.

Bản đồ được biểu diễn bởi một lưới ô vuông kích thước \(N \times M\), gồm \(N\) hàng (đánh số từ \(1\) đến \(N\)) và \(M\) cột (đánh số từ \(1\) đến \(M\)). Ô ở hàng \(i\), cột \(j\) được ký hiệu là \((i, j)\) và chứa một mỏ năng lượng có trữ lượng \(A_{i, j}\).

ByteBot xuất phát tại ô \((1, 1)\) và chỉ có thể di chuyển sang ô kề cạnh bên phải \((i, j + 1)\) hoặc ô kề cạnh phía dưới \((i + 1, j)\) để đến đích tại ô \((N, M)\). Như vậy, hành trình của p2o2HuaGiaBao sẽ đi qua đúng \(L = N + M - 1\) ô: \((r_1, c_1), (r_2, c_2), \dots, (r_L, c_L)\) với \((r_1, c_1) = (1, 1)\) và \((r_L, c_L) = (N, M)\).

Trên đường đi:

• Tại mỗi ô \((r_k, c_k)\) đi qua, p2o2HuaGiaBao thu nạp toàn bộ trữ lượng năng lượng \(A_{r_k, c_k}\).
• Tuy nhiên, mỗi bước di chuyển giữa hai ô liên tiếp từ \((r_k, c_k)\) sang \((r_{k+1}, c_{k+1})\), sự thay đổi đột ngột về độ cao năng lượng khiến động cơ tiêu hao một lượng năng lượng bằng độ chênh lệch tuyệt đối \(|A_{r_{k+1}, c_{k+1}} - A_{r_k, c_k}|\).

Tổng năng lượng tích lũy thực tế của hành trình được tính theo công thức:

Hãy giúp p2o2HuaGiaBao tìm một lộ trình hợp lệ để tổng năng lượng tích lũy đạt giá trị lớn nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N, M\) (\(1 \le N, M \le 1000\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) số nguyên không âm \(A_{i, j}\) (\(0 \le A_{i, j} \le 10^6\)).

Output

• In ra một số nguyên duy nhất là tổng năng lượng tích lũy lớn nhất mà ByteBot có thể đạt được.

Example

3 3
1 3 2
4 6 5
2 1 8

15

Scoring

• Subtask 1 (30 điểm): \(1 \le N, M \le 15\).
• Subtask 2 (70 điểm): \(1 \le N, M \le 1000\).