Máy cắt cỏ

Một khu vườn hình chữ nhật gồm $n$ hàng và $m$ cột. Các hàng được đánh số từ $1$ đến $n$ từ trên xuống dưới, các cột được đánh số từ $1$ đến $m$ từ trái sang phải. Ô nằm ở hàng $r$ cột $c$ được ký hiệu là $(r,c)$. Mỗi ô hoặc là cỏ sạch, hoặc là cỏ dại.

Bạn đứng cùng máy cắt cỏ tại ô góc trên bên trái $(1,1)$ và ban đầu đang quay mặt sang phải. Tại mỗi bước bạn thực hiện đúng một trong hai thao tác:

1. Đi một ô theo hướng đang quay mặt: nếu đang quay sang phải thì đi từ $(r,c)$ sang $(r,c+1)$, nếu đang quay sang trái thì đi từ $(r,c)$ sang $(r,c-1)$.
2. Đi xuống một ô, từ $(r,c)$ sang $(r+1,c)$, đồng thời đổi hướng quay mặt sang hướng ngược lại.

Bạn không được phép đi ra ngoài khu vườn. Một ô cỏ dại được cắt ngay khi bạn đứng trên ô đó, không phụ thuộc vào hướng đang quay mặt và việc cắt không tính là một bước đi.

Hãy tìm số bước đi ít nhất để cắt hết toàn bộ cỏ dại trong vườn.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số hàng và số cột của khu vườn.
• $n$ dòng tiếp theo, mỗi dòng chứa $m$ ký tự mô tả khu vườn. Ký tự G nghĩa là ô đó là cỏ sạch, ký tự W nghĩa là ô đó có cỏ dại.

Đảm bảo ô góc trên bên trái $(1,1)$ luôn là cỏ sạch.

Dữ liệu ra

In ra một số nguyên duy nhất: số bước đi ít nhất để cắt hết cỏ dại.

Ràng buộc

• $1\le n,m\le 150$
• Mỗi ký tự của lưới thuộc $\{$G, W$\}$
• Ô $(1,1)$ là G

Ví dụ