Bản đồ khu rừng được mô tả bởi một lưới ô vuông kích thước \(R imes C\). Khi đi vào ô vuông ở hàng \(i\), cột \(j\), bạn sẽ phải tiêu hao (hoặc được nạp lại nếu giá trị âm) một lượng năng lượng bằng \(A[i][j]\).

Hãy tìm lượng năng lượng tích lũy nhỏ nhất để đi từ góc trên bên trái \(((1, 1))\) đến góc dưới bên phải \(((R, C))\). Mỗi bước bạn chỉ được di chuyển sang một trong bốn ô kề cạnh (lên, xuống, trái, phải) và không được di chuyển ra ngoài lưới ô vuông. Bản đồ đảm bảo không chứa các hành trình nạp năng lượng vô hạn.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(R\) và \(C\) (\(1 \le R, C \le 100\)).
• \(R\) dòng tiếp theo, mỗi dòng chứa \(C\) số nguyên mô tả bảng năng lượng \(A\) (\(-1000 \le A[i][j] \le 1000\)).

Kết quả ra

• In ra một số nguyên duy nhất là lượng năng lượng tích lũy nhỏ nhất để hoàn thành chuyến đi.

Ví dụ

Input

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

Output

2