Cho ma trận ~n \times m~ gồm các số nguyên không âm ~c_{i,j}~ (chi phí khi đi vào ô đó).

Bạn bắt đầu ở ô ~(1,1)~ và muốn đến ~(n,m)~.

Mỗi bước chỉ được đi sang phải hoặc xuống dưới.

Tổng chi phí đường đi bằng tổng các ~(c_{i,j})~ của các ô đi qua (kể cả ô đầu và ô cuối).

Hãy tìm tổng chi phí nhỏ nhất.

Input

• Dòng 1: ~n, m~ trong đó ~(1 \le n,m \le 2000)~
• Tiếp theo ~n~ dòng, mỗi dòng ~m~ số ~c_{i,j}~ trong đó ~0 \le c_{i,j} \le 10^6~

Output

• Chi phí nhỏ nhất để đi từ ~(1,1)~ đến ~(n,m)~.

Ví dụ

Input

3 4
1 3 1 2
1 5 1 1
4 2 1 3

Output

8