Problem D

Down Went The Titanic

Time Limit: 8 Second

After the collision of the great Titanic with the iceberg, it went down. Now there are peoples floating in the cold water struggling with death. Some helping ship will arrive to save them. But they have to survive until the ships arrive. Now consider a water area with people, floating ices, large woods etc. Consider the following symbols:

* People staying on floating ice. People want to move from here as the floating ice cannot carry them for long time. Once a people move from here, the floating ice will get drowned. People can move to any of the four directions (north, east, west and south).

~ Water. People cannot go or move through them as water is extremely cold and not good enough for swimming.

. Floating ice. People can move to a floating ice. But floating ices are so light that they cannot float for long time, so people should move from here as soon as possible and once a people move from here, the floating ice will get drowned.

@ Large iceberg. People can move here but cannot stay here as they are extremely cold. These icebergs will remain floating all the time. Note that, no two people can stay on floating ice or large iceberg at the same time.

# Large wood. This place is safe. People can move and stay here until the helping ships arrive. A large wood will get drowned if more than P people stay on it at the same time.

Given the description of the area you have to find an optimal strategy that ensures the maximum number of living people.

Input:

The input contains a number of test cases. Each test case starts with a line containing three integers X, Y and P, where X, Y is the dimensions of the area (1 ≤ X, Y ≤ 30) and P (P ≤ 10) is the highest capacity of the large woods. Next X lines each contains Y characters. These lines contain no blank spaces or any characters other than asterisk (*), tilde (~), dot (.), at (@) and hash (#). Not more than 50% of the total area has a people. Input will terminate with end of file (EOF). There is a blank line between two consecutive test cases.

Output:

For each test case print one line of output, an integer denoting the maximum number of survivors possible.

SAMPLE INPUT

OUTPUT FOR SAMPLE INPUT

3 4 2

*~~#

...@

.~.*

3 5 1

~~*~~

#.@.#

~~*~~

1 4 2

**#~

Problemsetter: Ishtiak Zaman

Special Thanks To: Md. Mahbubul Hasan