After years of climbing the corporate ladder, you've finally landed your dream career as the Team Principal of Ferravi's F1 team. Nice work!

Your drivers are very rusty, and need to practise driving in straight lines. Unfortunately, because it's so late in the season, it's too late to find a professional track for this. Instead, you've found an old dirt trail for them to drive on.

The dirt trail is composed of ~n \times m~ tiles, where each tile has either dirt (D) or rock (R). For $1000, your pit crew can either turn a rock into dirt, or turn dirt into a rock.

Your drivers can only practise on the trail if there exists a non-empty contiguous range of columns such that every tile in those columns is dirt, and every tile outside them is rock. What is the minimum cost required to make the trail driveable?

Input

The first line contains two integers ~n~ and ~m~ ~(1 \leq n, m \leq 10^6)~, the number of rows and the number of columns on the trail.

The next ~n~ lines contain strings of length ~m~, where the ~i~th string represents the state of the ~i~th row the track. R represents rocks, and D represents dirt.

It is guaranteed that ~n \times m \leq 10^6~.

Output

Output the minimum cost required to make the trail driveable, in dollars.

Example

Input 1

4 4
RDRR
RDRD
DDRD
DRRD

Output 1

6000

Perform the following operations:

• Remove 2 rocks from the first column for $2000.
• Remove 1 rock from the second column for $1000.
• Add 3 rocks to the last column from $3000.

Now, there is a 2-column dirt path, and no other dirt, so the track is drivable. It can be shown that $6000 is the minimum cost required to acheive this.

Input 2

2 2
DD
DD

Output 2

0

No money needs to be spent, all the dirt is already in regular columns, covering the whole track.

Input 3

3 4
RRRR
RRRR
RRRR

Output 3

3000

You need at least one column of dirt, which you can create for $3000 by removing 3 rocks from any column in the track.