Cho một bảng số gồm ~m~ dòng, ~n~ cột, trên mỗi ô của bảng chứa số nguyên tùy ý ~a_{i,j}~. Từ một ô của bảng ta có thể di chuyển sang ô chung cạnh với nó. Một đường đi là một dãy các di chuyển qua các ô kề cạnh.

Hãy tìm một đường đi bắt đầu từ một ô nào đó thuộc mép trái (cột ~1~) của bảng sang một ô thuộc mép phải (cột ~n~) của bảng sao cho tổng các số của các ô đi qua là nhỏ nhất.

Input

Dòng đầu tiên chứa hai số nguyên dương ~m, n~ thỏa ~2 \le m, n \le 100~.

~m~ dòng tiếp theo, mỗi dòng chứa các phần tử ~a_{i,j}~ của bảng thỏa ~0 \le a_{i,j} \le 100, 1 \le i, j \le n~.

Output

In ra giá trị cần tìm.

Samples

Sample Input 1

5 6
8 1 1 1 1 1
9 1 9 0 6 7
6 1 0 5 8 8
7 9 1 2 6 4
1 1 1 4 7 0

Sample Output 1

11