Tý di chuyển trong một thành phố được mô tả bởi lưới ô vuông kích thước \(R \times C\).

Tại mỗi ô giao lộ \((i, j)\), có một đèn tín hiệu giao thông chỉ định hướng di chuyển ưu tiên của ô hiện tại:

• Ký tự \(H\) (Horizontal): Hướng ưu tiên nằm Ngang. Nếu di chuyển sang Trái hoặc Phải, chi phí chờ đèn là \(0\). Nếu di chuyển Lên hoặc Xuống, chi phí chờ đèn là \(1\).
• Ký tự \(V\) (Vertical): Hướng ưu tiên Dọc. Nếu di chuyển Lên hoặc Xuống, chi phí chờ đèn là \(0\). Nếu di chuyển sang Trái hoặc Phải, chi phí chờ đèn là \(1\).

Hãy tìm chi phí tối thiểu để Tý di chuyển từ ô xuất phát \((1, 1)\) đến ô đích \((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 một chuỗi ký tự độ dài \(C\) gồm các ký tự \(H\) và \(V\) mô tả hướng ưu tiên của các ô giao lộ.

Định dạng đầu ra

• Một số nguyên duy nhất là chi phí chờ đèn tối thiểu.

Ràng buộc

Ví dụ

Input:

3 3
HVH
VHH
HVV

Output:

1