Мышь нашла большой красивый торт и решила прогуляться по нему, попутно объедая ягоды на верхушке торта. Торт прямоугольный и разделен на аккуратные квадраты; в некоторых квадратах есть ягода, а в некоторых нет.
Мышь спешит, поэтому когда она взберется на торт в его северо-западном углу (вернняя левая клетка входных данных), она будет двигаться только на восток (направо) или на юг (вниз), пока не достигнет юго-восточного угла (нижняя правая клетка). Она съест все ягоды на клетках, через которые она пройдет, и оставит остальные ягоды нетронутыми.
Мышь хочет выбрать свой путь так, чтобы съесть наибольшее возможное количество ягод. Но, возможно, ее спешка и голод затмевают ее разум и вынуждают ее принимать неоптимальные решения...
Выходные данные
Выведите одно число - количество ягод, которые съест мышь, следуя своей стратегии.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
*..
.*.
..*
...
|
3
|
|
2
|
4 4
.*..
*...
...*
..*.
|
2
|
|
3
|
3 4
..**
*...
....
|
1
|
|
4
|
5 5
..*..
.....
**...
**...
**...
|
1
|