Mỗi ô trên một bàn cờ có kích thước ~n × m~ đều có một số không âm được viết lên. Quân vua muốn di chuyển từ góc dưới bên trái của bàn cờ đến góc trên bên phải, nhưng nó chỉ có thể đi lên, sang phải và đi chéo lên trên bên phải. Chi phí của việc đi vào một ô bằng với số được viết trên ô đó.

Nhiệm vụ của bạn là di chuyển quân vua từ góc dưới bên trái của bàn cờ đến góc trên bên phải với chi phí đường đi tối thiểu.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ ~(1 \le n,m \le 1000)~ - số dòng và số cột của bàn cờ.
• Tiếp theo gồm ~n~ dòng với mỗi dòng gồm ~m~ cột chứa các số nguyên ~a_i,_j~ ~(0 \le a_i,_j \le 1000)~ - số được viết trên ô ~i,j~.

Ô dưới cùng bên trái luôn được đảm bảo bằng ~0~.

Output

• Một số nguyên duy nhất là chi phí tối thiểu để đi từ ô dưới cùng bên trái lên ô trên cùng bên phải.

Sample Input 1

8 8 
9 9 9 9 9 9 1 9
9 9 9 9 9 1 9 2
9 9 9 9 9 9 1 9
9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9
0 9 9 9 9 9 9 9

Sample Output 1

56