Binbin's treasure map
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Binbin is a clever boy who likes to wear a skirt. One day, he saw some beautiful skirts on Taobao, but he had not enough money, which made him sad.

In order to make Binbin feel happy again, his's friend Xu1024 gave him a treasure map. The treasure map is composed of three characters:  '.',  '#',  '$'.

Character '.' indicates that this position is empty and passable;

Character '#' indicates that this position is blocked by a stone and not passable;

Character '$' indicates that this position has 1 coin on it and is passablle.

The locations outside the treasure map are all empty and passable.

Binbin can move up, down, left, and right, but not at an angle.
Firstly, Binbin can choose any grid as starting point.

Because Binbin wanted to wear a skirt so much, he had a chance to teleport to a certain grid as another starting point.

Binbin wanted to know how many coins he could eventually collect to buy skirts.

Can you help him?

输入描述:

The first line of each group contains two numbers N and M,(1<=N, M<=500), representing the number of rows and the number of columns of treasure map.

Then there are next N lines, each line contains M characters. which describe the terasure map.

输出描述:

Ouput a integer representing
the maxinum money Binbin would collected.
示例1

输入

复制 
4 4
.$.$
.##.
#$#.
.#.#

输出

复制 
3

说明

Binbin can start at point(1,1)  so he can collect 2 coins.

Then Binbin can teleport to point(3,2) so he can collect 1 coin.

Finally, Binbin would collect 3 coins.
示例2

输入

复制 
4 4
.#$#
####
..$$
$$$$

输出

复制 
7

说明

Binbin can start at point(1,3)  so he can collect 1 coin.

Then Binbin can teleport to point(3,2) so he can collect 6 coins.

Finally, Binbin would collect 7 coins.