Tree Investment

Sangdo, who made a fortune through real estate investment, recently bought a plot of land of size N×N. To make the land easy to manage, Sangdo divided it into 1×1 cells. Each cell is denoted (r, c), where r is the number of cells from the top and c is the number of cells from the left. r and c both start at 1.

Sangdo, an electronic and telecommunications engineering graduate, built a robot named S2D2 that inspects the nutrients in the land. S2D2 inspects the nutrients in each 1×1 cell, sends the result to Sangdo, and does this for every cell. Initially, every cell contains 5 nutrients.

One day, while enjoying the satisfaction of looking over his wide land every day, a thought occurred to him.

Let's do tree investment!

Tree investment is a way to buy small saplings, grow them for a while, then sell them for profit. To earn even more money through tree investment, Sangdo bought M trees and planted them in the land. Multiple trees may be planted in the same 1×1 cell.

These trees go through the four seasons, repeating the following process.

In spring, a tree eats nutrients equal to its age, and its age increases by 1. Each tree can only eat nutrients in the 1×1 cell where it is located. If there are multiple trees in one cell, trees eat starting from the youngest. If a tree cannot eat nutrients equal to its age because the land does not have enough, it eats nothing and dies immediately.

In summer, trees that died in spring turn into nutrients. For each dead tree, the value of its age divided by 2 is added as nutrients to the cell where the tree was located. The decimal part is discarded.

In autumn, trees reproduce. A tree reproduces only if its age is a multiple of 5, and a tree of age 1 is born in each of the 8 adjacent cells. The cells adjacent to a cell (r, c) are (r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1, c+1). No tree is born in a cell outside Sangdo's land.

In winter, S2D2 moves around the land and adds nutrients to it. The amount of nutrients added to each cell is A[r][c], which is given in the input.

Write a program that finds the number of trees alive in Sangdo's land after K years.

The first line gives N, M, K.

N lines follow, giving the values of the array A. The c-th value in the r-th line is A[r][c].

The next M lines each give three integers x, y, z describing a tree Sangdo planted. The first two integers are the tree's location (x, y), and the last integer is the tree's age.

Print the number of trees that survive after K years on the first line.

• 1 ≤ N ≤ 10
• 1 ≤ M ≤ N2
• 1 ≤ K ≤ 1,000
• 1 ≤ A[r][c] ≤ 100
• 1 ≤ age of each tree given in the input ≤ 10
• All locations of the trees given in the input are distinct

The content related to tree investment was referenced from this link.