Under construction

Still being built. Things may change

Fine Dust, Goodbye!

Interview

Time limit1sMemory limit512 MB

Summary
Simulate T seconds of dust diffusion on a grid plus the circular wind from a two-cell air purifier, then sum the remaining dust.
Level

Medium7 of 10

Topics
Simulation, Implementation, Array, Matrix
Solved
No attempts yet

Problem

Gusagwa is going to install an air purifier to remove fine dust. To test the purifier's performance, Gusagwa represented his house as an R×C grid, split into 1×1 cells. Using his excellent coding skills, Gusagwa developed a system that monitors the amount of fine dust in each cell (r, c) in real time. (r, c) means row r, column c.

The air purifier is always installed in column 1, and it occupies two rows. Cells without the air purifier contain fine dust, and the amount of fine dust in (r, c) is Ar,c.

During one second, the following events occur in order.

  1. The fine dust spreads. Spreading occurs simultaneously in every cell that has fine dust.

    • The fine dust in (r, c) spreads in the four adjacent directions.
    • If an adjacent direction has the air purifier, or there is no cell there, spreading does not occur in that direction.
    • The amount spread is Ar,c/5, with the fractional part discarded. That is, ⌊Ar,c/5⌋.
    • The amount of fine dust remaining in (r, c) is Ar,c - ⌊Ar,c/5⌋×(number of directions spread).

  2. The air purifier operates.

    • The air purifier blows out wind.
    • The wind from the upper air purifier circulates counterclockwise, and the wind from the lower air purifier circulates clockwise.
    • When the wind blows, all fine dust moves one cell in the direction of the wind.
    • The wind blown from the air purifier contains no fine dust, and all fine dust that enters the air purifier is purified.

The following are examples of spreading.

Because there are no cells to the left and above, spreading occurred in only two directions.

Spreading occurs in all four adjacent directions.

Spreading does not occur into the cell with the air purifier.

The air purifier's wind circulates in the following directions.

Given the information about the room, find the amount of fine dust remaining in Gusagwa's room after T seconds.

Input

The first line gives R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000).

From the second line, R lines give Ar,c (-1 ≤ Ar,c ≤ 1,000). Where the air purifier is installed, Ar,c is -1, and the other values are amounts of fine dust. The two -1s are attached vertically, and are at least two cells away from the top row and the bottom row.

Output

On the first line, output the amount of fine dust remaining in Gusagwa's room after T seconds.

Examples5

  1. Example 1

    Input
    7 8 1
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
    Expected output
    188

  2. Example 2

    Input
    7 8 2
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
    Expected output
    188

  3. Example 3

    Input
    7 8 3
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
    Expected output
    186

  4. Example 4

    Input
    7 8 4
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
    Expected output
    178

  5. Example 5

    Input
    7 8 5
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
    Expected output
    172