You are awful at gardening. Your garden is full of grass and weeds exclusively. Your garden is an \(n \times m\) grid. Each garden cell contains either grass (
G) or weeds (
You have borrowed a lawn-mower and wish to yeet the weeds. Initially, you stand in the top-left corner of your garden facing right. At each time-step, you either move one cell in the direction you face (left or right) or move one cell down and change direction (moving down is the only way you can change direction). You cannot leave the garden, if you occupy a space with weeds in it at any time it is mowed (turned into grass) and you always start in the top-left corner facing right.
What is the minimum number of moves needed to mow all the weeds?
The first line contains two integers \(n, m (1\leq n,m \leq 1500)\), the number of rows and columns respectively.
The following \(n\) lines contain \(m\) characters, each is either
G denoting grass or
W denoting weeds.
It is guaranteed the top-left corner of your garden will contain grass.
A single integer
Sample Input 1
4 5 GWGGW GGWGG GWGGG WGGGG
Sample Output 1
Sample Input 2
3 3 GWW WWW WWG
Sample Output 2