Rotten Berries

Submit solution

Points: 25
Time limit: 1.0s
Python 3 4.0s
Memory limit: 256M

Problem type

Safae is storing her raspberries in the refrigerator, You can think of her refrigerator as an \(n\) by \(m\) Two-Dimensional grid.

Each cell of the grid contains either:

  • an empty cell represented by a dot ('.').
  • a fresh raspberry represented by the letter 'o'.
  • a rotten raspberry represented by the letter 'x'.

Safae will take \(d\) days vacation. Because some of the strawberries were rotten, they will damage some of the fresh raspberries. In fact, at the end of each day, each rotten raspberry will damage the adjacent fresh raspberries.

Your task is to determine how many fresh raspberries are in Safae's refrigerator after she returns from her vacation (after \(d\) days have passed).

Please note that rottenness cannot travel through empty cells, that is a rotten raspberry cannot affect an adjacent empty cell.

Input Specification

the first line of the input consists of n and m (\(1 \le n, m \le 100\)), the number of rows and columns in the refrigerator respectively.

n lines follow where each contains m characters representing the n-th row of the refrigerator.

the next line of the input contains one single integer (\( 1\le d \le 1000\)) representing the number of days Safae took as a vacation.

Output Specification

Output one single Integer the number of remaining fresh raspberries in Safae's Refrigerator.

Sample Input

3 3

Sample Output


Sample Input

3 3

Sample Output



There are no comments at the moment.