VNOI Marathon 08

In the adventure of collecting the Deathly Hallows, Harry and his friends found a secret chamber. Suddenly, when they had just entered, walls appeared everywhere, divided the chamber into N*N rooms. The team then was split into several rooms. Every room was equal in size and had 4 doors, each of which was on a wall of the room.

Monsters then appeared in the rooms contained people. The number of monsters was equal to the number of people in that room, which meant when a person moved from room X to room Y, a new monster immediately appeared in room Y.

Harry and his friends had to fight the monsters and find paths to escape. They found that the time to kill a monster in the room (I, J) was A[i, j]. (The rooms were numbered from left to right, and from above to below). One person could fight only one monster in a room at the same time; after killing a monster, (s)he could move to one of the adjacent rooms immediately. However, in case (s)he stayed, another monster would appear immediately.

With the Marauder's Map, Harry knew which rooms his friends were confined. He also discovered that these rooms were painted with different colors. Moreover, the doors on the walls of the chamber also had different colors. Harry had to guide each of his friends, one after another, to run to the door which had the same color with the room confined that person. But when a person escaped, immediately, the monsters would regained their lost energy (or the monsters would be strong as it'd just appeared) and the walls of the chamber rotated a unit clockwise. Also, the doors on them also went with them, as described on the figures below.

Because of the difficult situation, Harry could only guide the next friend after the current one had escaped the maze. Please help Harry to guide all his friends escaped the chamber in minimum time.

(P.s: If you ask me ‘How could Harry guide his friends?’ Yeah, he used the ‘Sonorus!’ incantation. It made his voice resounded everywhere in the chamber. :D)

Input

• The first line contains 2 positive integer N, K. N is the dimension of the maze, and K is the number of members in Harry’s Team.
• The I-th line of the the next N lines contains N non-negative integers. The J-th number in line I is A[I, J] representing the time required to kill a monster in the room (I, J).
• Each line in the next K lines contains 3 non-negative integers I, J, C, which means the Xth person is in the room (I, J) and this room is painted with color C.
• The last line contains 4*N non-negative integers which are the colors of the doors on 4 walls enclosed the maze. The colors, one after another clockwise, start from the door on the upper wall of the room (1,1). (Order similar to Figure 1).

Output

A single integer that is the minimum time for Harry and all of his friends to escape the maze.

Constrains

• 1 ≤ N ≤ 100
• 1 ≤ K ≤ 100, K ≤ N^2
• 0 ≤ C ≤ 100
• 0 ≤ A[I, J] ≤ 100

Example

Input
3 2
2 2 2
0 2 0
1 0 2
1 2 2
2 1 2
2 2 2 2 2 2 1 1 2 1 1 2

Output
3

A valid way to escape:

- The person (1,2) kills his monster in 2 seconds, then escapes the chamber by moves to (0,2). While (2,1) fighting his monster. He can kill it, but he can't move, so the monster appears again.

- The chamber rotates. The monster at (2,1) regains its health.

- The person (2,1) kills his monster in 0 second, and moves to (3,1). He kills the monster at (3,1) in 1 seconds, then escapes the chamber by moves to (3,0).

Total Time = 2+0+1 = 3.