Fishing King

Interview

Time limit1sMemory limit512 MB

Summary
A fisherman sweeps columns left to right, catching the lowest shark in each column while the rest slide and bounce vertically or horizontally, merging sharks that collide.
Level

Medium6 of 10

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

Problem

The place where the Fishing King goes shark fishing can be represented as an R×C grid. Each cell of the grid is denoted by (r, c). r is the row, c is the column, and (R, C) is the bottom-right cell in the figure below. A cell can contain at most one shark. Each shark has a size and a speed.

Initially, the Fishing King is one cell to the left of column 1. The following events happen during 1 second, in the order listed below. The Fishing King stops moving when he moves to the cell to the right of the rightmost column.

  1. The Fishing King moves one cell to the right.
  2. Among the sharks in the column where the Fishing King is, he catches the shark closest to the ground. When he catches a shark, the caught shark disappears from the grid.
  3. The sharks move.

A shark moves at the speed given in the input, and the unit of speed is cells per second. If the cell a shark is trying to move to is beyond the boundary of the grid, it reverses direction and moves while maintaining its speed.

From the state in the left figure, after 1 second passes, the state becomes the right figure. The direction a shark faces is the direction of its velocity, and the integer written at the bottom-left is its speed. A letter is written at the top-left to distinguish the sharks.

After the sharks finish moving, a cell can contain two or more sharks. In that case, the shark with the largest size eats all the other sharks.

Given the state of the grid where the Fishing King goes shark fishing, find the sum of the sizes of the sharks the Fishing King catches.

Input

The first line gives the size of the grid R, C and the number of sharks M. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)

From the second line, M lines give information about the sharks. Each shark's information consists of five integers r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000). (r, c) is the shark's position, s is its speed, d is its direction of movement, and z is its size. If d is 1 it means up, if 2 it means down, if 3 it means right, and if 4 it means left.

No two sharks have the same size, and no cell contains two or more sharks.

Output

Output the sum of the sizes of the sharks the Fishing King catches.

Examples4

  1. Example 1

    Input
    4 6 8
4 1 3 3 8
1 3 5 2 9
2 4 8 4 1
4 5 0 1 4
3 3 1 2 7
1 5 8 4 3
3 6 2 1 2
2 2 2 3 5
    Expected output
    22

  2. Example 2

    Input
    100 100 0
    Expected output
    0

  3. Example 3

    Input
    4 5 4
4 1 3 3 8
1 3 5 2 9
2 4 8 4 1
4 5 0 1 4
    Expected output
    22

  4. Example 4

    Input
    2 2 4
1 1 1 1 1
2 2 2 2 2
1 2 1 2 3
2 1 2 1 4
    Expected output
    4