Lan chơi một trò chơi trên bảng ô vuông gồm $n$ hàng $m$ cột. Ban đầu, Lan đứng ở góc trên bên trái của bảng (hàng 1, cột 1), và cần đi tới góc dưới bên phải (hàng $n$ , cột $m$ ).

Quy tắc di chuyển của Lan như sau:

• Không được đi tới hàng có chỉ số nhỏ hơn hàng hiện tại, cũng không được đi tới cột có chỉ số nhỏ hơn cột hiện tại;

• Khoảng cách mỗi bước đi không vượt quá 3 (khoảng cách được định nghĩa như sau: nếu đang ở $(r,c)$ , bước tiếp theo chỉ được đi tới các vị trí thỏa mãn $0 \le (r'-r) + (c'-c) \le 3$ , $r' \ge r$ , $c' \ge c$ và $(r',c') \ne (r,c)$ ).

Mỗi vị trí trên bảng có một trọng số (thưởng là số dương, phạt là số âm); đi tới vị trí nào thì nhận được trọng số của vị trí đó. Lan muốn tổng trọng số trên đường đi từ điểm xuất phát tới đích là lớn nhất, hãy tìm tổng trọng số lớn nhất này.

Dữ liệu vào

Dòng đầu tiên của input gồm hai số nguyên $n, m$ ( $1 \le n, m \le 100$ ), là kích thước của bảng ô vuông.

$n$ dòng tiếp theo, mỗi dòng gồm $m$ số nguyên, là trọng số của từng vị trí trên bảng ( $-10^4 \le$ trọng số $\le 10^4$ ).

Dữ liệu ra

In ra một số nguyên, là tổng trọng số lớn nhất trên đường đi từ điểm xuất phát tới đích.

Ví dụ

Input

3 5
-4 -5 -10 -3 1
7 5 -9 3 -10
10 -2 6 -10 -4

Output

15