Training Site

# Counting Islands

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 32 megabytes
Time limit: 1.0 seconds

New Zealand is a country located in the southwestern Pacific Ocean, comprising of about 600 islands. However, there are only two main islands.

Given a map of an arbitrary ocean, determing how many main islands (islands with area not less than some threshold $T$) are in it.

## Input

The first line of input contains three integers, $W$, $H$, and $T$ ($1 \leq W, H \leq 1000, 1 \leq T \leq W \times H$), describing the width and height of the map in kilometers and the threshold for main island status in square kilometers, respectively.

The following $H$ lines each contain $W$ characters, representing the map of ocean. A # character denotes a square kilometer of land, and a . character denotes a square kilometer of ocean. Islands do not connect diagonally.

## Output

Output should be a single line with a single integer - the number of main islands depicted in the map.

• Subtask 1 ($20\%$): Every island has an area of $1$ square kilometer; is represented by a single # character
• Subtask 2 ($20\%$): $W, H \leq 20$
• Subtask 3 ($60\%$): No further restrictions
• ### Sample Input 1

5 5 1
.#...
...#.
..#..
.#...
...#.


### Sample Output 1

5

• ### Sample Input 2

20 17 15
....................
..........##........
...........###......
............###...##
.............#######
............###.####
.............#####..
.........##....##...
........#####.......
.......#####........
.....#####..........
...######...........
.######.............
.#####..............
..###...............
#...................
....................


### Sample Output 2

2