Cho một ma trận gồm n hàng và m cột, mỗi ô có một giá trị biểu thị chi phí đi qua ô đó.

Bạn bắt đầu tại ô (0, 0) (góc trên bên trái) và muốn đi đến ô (n-1, m-1) (góc dưới bên phải).

Tại mỗi bước, bạn chỉ được phép đi sang phải hoặc đi xuống dưới.

Hãy tìm tổng chi phí nhỏ nhất để đi từ ô (0, 0) đến ô (n-1, m-1).

Dữ liệu vào (Input)

Dòng đầu chứa hai số nguyên n, m (1 ≤ n, m ≤ 100).

Tiếp theo là n dòng, mỗi dòng chứa m số nguyên (|cost[i][j]| ≤ 10⁴) — là chi phí của từng ô.

Dữ liệu ra (Output)

In ra một số nguyên duy nhất — là tổng chi phí nhỏ nhất.

Ví dụ:

Input

3 3
1 3 1
1 5 1
4 2 1

Output

7

Giải thích:

Đường đi tối ưu: 1 → 3 → 1 → 1 → 1 (Tổng = 7)