Minimum Watering Moves

You are given a garden represented as an ( n \times m ) grid. Each cell of the grid is either a plant (denoted by 1) or empty (denoted by 0). A watering move is performed by selecting a plant and watering all plants that lie within a Manhattan distance of ( r ) from the selected cell. The Manhattan distance between two cells ( (x_1, y_1) ) and ( (x_2, y_2) ) is defined as ( |x_1 - x_2| + |y_1 - y_2| ).

Your task is to calculate the minimum number of watering moves required to water all the plants in the garden. The input contains multiple test cases, and the set of test cases terminates when a test case with ( n = 0 ), ( m = 0 ), and ( r = 0 ) is encountered (this test case should not be processed).

Note: You must read input from standard input (stdin) and write the output to standard output (stdout).

inputFormat

The input consists of multiple test cases. Each test case starts with a line containing three integers ( n ), ( m ), and ( r ) — the number of rows, columns, and the watering range, respectively. This is followed by ( n ) lines, each containing ( m ) integers (either 0 or 1) that represent the garden grid. The sequence of test cases terminates with a line containing "0 0 0", which should not be processed.

outputFormat

For each test case, output a single line containing the minimum number of watering moves required to water all the plants.## sample

3 3 1
1 0 0
0 1 0
0 0 1
0 0 0

3