Castle Defense

Time limit1sMemory limit512 MB

Summary
Place 3 archers on the wall row so that the total number of enemies killed by their attacks before reaching the wall is maximized.
Level

Medium7 of 10

Topics
Brute force, Simulation, Implementation, Array
Solved
No attempts yet

Problem

Castle Defense is a turn-based game in which you kill enemies that swarm toward your castle. The game takes place on a grid of size N×M. The grid is divided into 1×1 cells, and each cell contains at most one enemy. Every cell in the row directly below row N (row N+1) contains a castle wall.

You want to place 3 archers to defend the castle from the enemies. An archer can be placed in a cell that contains the castle wall, and each cell can hold at most 1 archer. On each turn, an archer can attack one enemy, and all archers attack at the same time. The enemy an archer attacks is the closest enemy whose distance is at most D; if there are several such enemies, the archer attacks the leftmost one. The same enemy can be attacked by several archers. An attacked enemy is removed from the game. After the archers finish attacking, the enemies move. An enemy moves one cell down, and if it moves into a cell that contains the castle wall, it is removed from the game. The game ends when every enemy is removed from the grid.

As the description shows, the game plays out in a fixed way once the archers are placed. Therefore the positions of the archers matter in this game. Given the state of the grid, compute the maximum number of enemies that can be removed by the archers' attacks.

The distance between two positions (r1, c1) and (r2, c2) on the grid is |r1-r2| + |c1-c2|.

Input

The first line gives the number of grid rows N, the number of columns M, and the archers' attack range limit D. From the second line, N lines give the state of the grid. 0 is an empty cell, and 1 is a cell with an enemy.

Output

On the first line, print the maximum number of enemies that can be removed by the archers' attacks.

Constraints

  • 3 ≤ N, M ≤ 15
  • 1 ≤ D ≤ 10

Examples5

  1. Example 1

    Input
    5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
    Expected output
    3

  2. Example 2

    Input
    5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0
    Expected output
    3

  3. Example 3

    Input
    5 5 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0
    Expected output
    5

  4. Example 4

    Input
    5 5 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
    Expected output
    15

  5. Example 5

    Input
    6 5 1
1 0 1 0 1
0 1 0 1 0
1 1 0 0 0
0 0 0 1 1
1 1 0 1 1
0 0 1 0 0
    Expected output
    9