Under construction

Still being built. Things may change

Magician Shark and Rain Dance

Time limit1sMemory limit1024 MB

Summary
Simulate M rounds of cloud movement on a toroidal N by N grid, add rain and diagonal water, then form new clouds where water is at least 2, and print the total water.
Level

Medium4 of 10

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

Problem

Magician Shark can cast Fireball, Tornado, Firestorm, and Water Copy Bug magic. The spell he learned today is Rain Dance. Casting Rain Dance creates rain clouds in the sky. Today he will practice Rain Dance on an N×N grid. Each cell of the grid holds one basket, and the basket fills the whole cell. There is no limit on the amount of water a basket can hold. (r, c) denotes the basket in row r and column c of the grid, and A[r][c] denotes the amount of water stored in the basket at (r, c).

The top-left cell of the grid is (1, 1) and the bottom-right cell is (N, N). For practice, Magician Shark connected row 1 with row N and column 1 with column N. That is, below row N lies row 1, above row 1 lies row N, to the left of column 1 lies column N, and to the right of column N lies column 1.

Casting Rain Dance creates rain clouds at (N, 1), (N, 2), (N-1, 1), and (N-1, 2). A cloud fills the whole cell. He will now command the clouds to move M times. The i-th move command consists of a direction di and a distance si. There are 8 directions, represented by 8 integers. Starting from 1, they are ←, ↖, ↑, ↗, →, ↘, ↓, ↙. When a move is commanded, the following happens in order.

  1. Every cloud moves si cells in direction di.

  2. Rain falls from each cloud, and the amount of water in the basket of the cell containing the cloud increases by 1.

  3. Every cloud disappears.

  4. Water Copy Bug magic is cast on each cell (r, c) where water increased in step 2. Water Copy Bug magic increases the amount of water in the basket at (r, c) by the number of baskets with water in cells at diagonal distance 1.

    • Here, unlike movement, a cell that crosses the boundary is not a cell at diagonal distance 1.
    • For example, the adjacent diagonal cells of (N, 2) are (N-1, 1) and (N-1, 3), and the only adjacent diagonal cell of (N, N) is (N-1, N-1).

  5. Clouds form on every cell whose basket holds at least 2 water, and the amount of water decreases by 2. Here, a cell where a cloud forms must not be a cell where a cloud disappeared in step 3.

Find the sum of the amounts of water in the baskets after all M moves finish.

Input

The first line gives N and M.

From the second line, N lines each give N integers. The c-th integer of the r-th line denotes A[r][c].

The next M lines each give the information of one move, di and si, in order.

Output

On the first line, print the sum of the amounts of water in the baskets after all M moves finish.

Constraints

  • 2 ≤ N ≤ 50
  • 1 ≤ M ≤ 100
  • 0 ≤ A[r][c] ≤ 100
  • 1 ≤ di ≤ 8
  • 1 ≤ si ≤ 50

Examples3

  1. Example 1

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

  2. Example 2

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

  3. Example 3

    Input
    5 8
100 100 100 100 100
100 100 100 100 100
100 100 100 100 100
100 100 100 100 100
100 100 100 100 100
8 1
7 1
6 1
5 1
4 1
3 1
2 1
1 1
    Expected output
    2657