Cho ma trận kích thước ~n \times n~, trên mỗi ô có gán giá trị ~a_{i,j}~. Viết chương trình tìm đường đi xuất phát từ ô trái trên đến ô phải dưới theo quy tắc đi qua phải hoặc đi xuống dưới sao cho tổng giá trị các ô trên đường đi là nhỏ nhất.

Input

Dòng thứ nhất chứa hai số nguyên dương ~n, m~ thỏa ~1 \le n, m \le 1000~.

~n~ dòng tiếp theo mỗi dòng chứa ~m~ số nguyên dương ~a_{i,j}~ của ma trận thỏa ~a_{i,j} \le 500~.

Output

In ra kết quả cần tìm.

Samples

Sample Input 1

3 4
5 9 4 3
3 1 6 9
8 6 8 12

Sample Output 1

35