Tèo đang tham gia trò chơi vượt chướng ngại vật trên một lưới các ô đất kích thước \(R \times C\). Ô đất ở hàng \(i\), cột \(j\) có độ cao là \(H[i][j]\).

Từ ô hiện tại \((r, c)\), Tèo có thể di chuyển sang một ô kề cạnh \((nr, nc)\) (chung cạnh). Quy tắc tính chi phí di chuyển như sau:

• Nếu ô kề cạnh có độ cao nhỏ hơn hoặc bằng độ cao ô hiện tại (\(H[nr][nc] \le H[r][c]\)): Tèo chỉ cần trượt xuống hoặc đi ngang, chi phí bằng \(0\).
• Nếu ô kề cạnh có độ cao lớn hơn độ cao ô hiện tại (\(H[nr][nc] > H[r][c]\)): Tèo phải leo lên cao, chi phí bằng \(1\).

Hãy tìm chi phí tối thiểu để Tèo di chuyển từ ô \((1, 1)\) đến ô \((R, C)\).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(R\) và \(C\) (\(1 \le R, C \le 1000\)).
• \(R\) dòng tiếp theo, mỗi dòng chứa \(C\) số nguyên mô tả độ cao \(H[i][j]\) (\(0 \le H[i][j] \le 10^6\)).

Định dạng đầu ra

• Một số nguyên duy nhất là chi phí di chuyển nhỏ nhất.

Ràng buộc

Ví dụ

Input:

3 3
1 3 2
2 2 4
1 3 3

Output:

2