After dealing with his ~N~ by ~M~ grid for too long, Santa asks you to find the minimum number of cookies he must eat to travel from ~(1, 1)~ to ~(N, M)~.
He can also only travel to cells that share a side with his current cell (i.e., not diagonally).
Each cell can either be an open space, denoted by
., or a cookie, denoted by
Whenever he enters a cell with a cookie, he always eats it.
Since Santa wants to maintain his slim figure, help him find the minimum number of cookies he needs to eat to travel from the top-left corner to the bottom-right corner!
The first line will contain ~N~ ~(1 \leq N \leq 1\,000)~ and ~M~ ~(1 \leq M \leq 1\,000)~, the number of rows and the numbers of columns in his grid.
The next ~N~ lines will each contain ~M~ cells.
Output the minimum amount of cookies that must be collected to travel from ~(1, 1)~ to ~(N, M)~.
Sample Input 1
6 4 C..C .CCC CC.C ..CC CC.. C.C.
Sample Output 1
Sample Input 2
5 5 ..... ..CC. ..... ..... .....
Sample Output 2