Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

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.

Subtasks

The following subtasks are available:

  • 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