405035: GYM101744 M MaratonIME returns home

Popular among the most traditional coders, the Summer Camp is famous for its fancy parties. After each party all attendees must return to their homes, but the way back home is not always easy: mildly drunk coders walk weird and often find or lose money along the way. However, MaratonIME always has a sober member in the group, who assures no one will lose money, except when they are robbed.

On its way back MaratonIME knows that they can call their coach, Renzo, who will pick them up immediately. Instead of doing that right after the party, they want to know what is the maximum amount of money they can carry back to their homes.

Your task is to write a program that solves this problem. Consider the following facts:

1. The city map can be seen as an N by M grid;
2. Members of MaratonIME are initially at the top left corner, and start walking right, carrying no money;
3. Whenever they reach the end of a row, they walk to the row below and start walking in the opposite direction (if they were walking right, they walk left the next row, and vice-versa);
4. They cannot go past the last row;
5. Whenever they meet a burglar, they lose all their money;
6. They can call Renzo at anytime, and he will pick them up instantly.

The first line of the input contains two integers N and M (1 ≤ N, M ≤ 10³), respectively, the number of rows and columns of the grid. Then follows N lines, each containing M characters, representing the city map. Each cell of the city map can be either:

• , meaning there is nothing at this cell of the grid;
• , meaning there is a coin worth 1 unit of money at this cell;
• , meaning there is a burglar at that cell.

The output must contain a single integer: the maximum amount of money MaratonIME can carry back home.

3 3
__.
_._
L._

2

In the example above, MaratonIME follows the following path: (1, 1) (1, 2) (1, 3) (2, 3) (2, 2) (2, 1) (3, 1) (3, 2) (3, 3). When they reach (2, 2) or (2, 1) they will have 2 coins, and that is the highest value they can get before calling Renzo.