Magician Shark and Fireball

Interview

Time limit1sMemory limit512 MB

Summary

Simulate fireballs moving on a wrapping N by N grid for K steps, merging any that share a cell and splitting each merged group into four.

Level: Medium5 of 10
Topics: Simulation, Implementation, Array, Math
Solved: No attempts yet

Problem

Adult Shark became a magician and learned Fireball.

Magician Shark launched M fireballs onto an N×N grid. Initially, each fireball waits at its own position to move. Fireball i is at (ri, ci), has mass mi, direction di, and speed si. Position (r, c) means row r, column c.

The rows and columns of the grid are numbered from 1 to N, and row 1 is connected to row N, while column 1 is connected to column N.

The direction of a fireball means one of the 8 directions adjacent to a cell, written as integers as follows.


7	0	1
6		2
5	4	3

When Magician Shark orders all fireballs to move, the following happens.

Every fireball moves si cells in its own direction di.
- During movement, several fireballs may occupy the same cell.
After all movement ends, in any cell containing 2 or more fireballs the following happens.
1. All fireballs in the same cell merge into one.
2. The fireball splits into 4 fireballs.
3. The mass, speed, and direction of the split fireballs are as follows.
  1. Mass is ⌊(sum of masses of the merged fireballs)/5⌋.
  2. Speed is ⌊(sum of speeds of the merged fireballs)/(number of merged fireballs)⌋.
  3. If the directions of the merged fireballs are all odd or all even, the directions are 0, 2, 4, 6; otherwise they are 1, 3, 5, 7.
4. A fireball with mass 0 disappears.

Find the sum of the masses of the fireballs remaining after Magician Shark orders movement K times.

Input

The first line gives N, M, and K.

From the second line, M lines each give the information of one fireball. The information consists of five integers ri, ci, mi, si, di.

No two fireballs are given at the same position in the input.

Output

Print the sum of the masses of the fireballs remaining after Magician Shark orders movement K times.

Constraints

4 ≤ N ≤ 50
0 ≤ M ≤ N2
1 ≤ K ≤ 1,000
1 ≤ ri, ci ≤ N
1 ≤ mi ≤ 1,000
1 ≤ si ≤ 1,000
0 ≤ di ≤ 7

Examples4

Example 1
Input
```
4 2 1
1 1 5 2 2
1 4 7 1 6
```
Expected output
```
8
```
Example 2
Input
```
4 2 2
1 1 5 2 2
1 4 7 1 6
```
Expected output
```
8
```
Example 3
Input
```
4 2 3
1 1 5 2 2
1 4 7 1 6
```
Expected output
```
0
```

Example 4

Input

Expected output