Cho bảng số có kích thước ~m*n~, các số trên bảng có giá trị dương.

Ban đầu người chơi đang đứng ở ô ~(1, 1)~ và cần phải đi đến ô ~(m, n)~. Người chơi có thể di chuyển theo ~1~ trong ~2~ cách sau:

• Tiến lên: Di chuyển từ ô ~(i, j)~ tới ô ~(i+1, j+1)~.
• Lùi lại: Di chuyển tới ô bên trái ~(i, j-1)~ hoặc phía trên ~(i-1, j)~.

Lưu ý: Không được phép đi lùi 2 lần liên tiếp và không được đi qua những ô đã bị đi qua rồi.

Yêu cầu

Tính tổng con đường nhỏ nhất để đi đến ~(m,n)~ (tổng tất cả các số trên các ô đã đi qua bao gồm cả ô bắt đầu và ô kết thúc).

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~m~, ~n~ ~(2≤m,n≤10^3)~.
• m dòng sau, mỗi dòng chứa ~n~ số nguyên dương ~a_{ij}~ (~a_{ij}≤10^9~) mô tả giá trị của các ô trong bảng.

Output

Một dòng duy nhất là tổng giá trị của con đường bé nhất tìm được.

Sample Input

3 4
1 2 1 4
1 1 1 1
1 1 10 1

Sample Output

6

Subtask

• Có 50% số test ứng với 50% số điểm có ~1≤m,n≤100~;
• 50% số test còn lại tương ứng với 50% số điểm không có giới hạn gì thêm.