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 (W).

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?

Input Specification

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.

Output Specification

A single integer

Sample Input 1

4 5
GWGGW
GGWGG
GWGGG
WGGGG

Sample Output 1

11

Sample Input 2

3 3
GWW
WWW
WWG

Sample Output 2

7