Start: Dec, 22, 2016 22:05:00
2016年秋季学期程序设计基础第三次考试(补题)
End: Jan, 05, 2017 02:00:00
Time elapsed:
Time remaining:

杭师大的圣诞树 2190

Time Limit:  1 s      Memory Limit:   256 MB
Submission:110     AC:37     Score:1

Description

圣诞将至,学校(某人)准备出资订购一批圣诞树发给教学班当作圣诞礼物,作为今天考试的额外奖励。

虽然学校很有钱可是并不会挑圣诞树,也不想搬运圣诞树。

于是这个购买圣诞树的任务就丢到了伐木工Landy的头上。Landy其实也不会挑圣诞树,但是为了避免学校挑剔之后不付钱,他打算将伐木场内所有的树都带来让学校挑选,但是圣诞节将至,时间紧迫,Landy需要在最短的时间内砍光伐木场内的树木。

为了简化题目,我们将伐木场抽象一个n*m的矩形,矩形内使用字符’T’代表此位置存在一棵树,字符’.’代表此处没有东西。

一开始Landy站在左上角(0,0)的位置,初始方向向右 。(0,0)位置的树不用走就能砍掉。

他在每个时刻只能做以下两种操作之一:

  1. 在当前方向上移动一格;
  2. 往下走一行,并改变方向(左->右,右->左)。(注意:走到下一行就回不到上一行,同一行不能回头。)

现在Landy需要知道,他最少需要走多少格才能将伐木场的树木全部砍光。

Input

输入有多组,第一行存在两个数字n,m代表这个伐木场的大小(0<n,m<150)

接下来n行,每行给出m个字符,描述整个伐木场的树木分布。(注意字符的读入。)

Output

输出一个整数,代表Landy最少需要走多少格才能将伐木场的所有数目砍光。

Samples

input
1 1 T
output
0
input
2 2 TT TT
output
3
input
3 3 TTT .T. T..
output
6
input
4 4 TTTT .... TTTT ....
output
11