Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NHP - Harry Potter and the Deathly Maze

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.


Được gửi lên bởi:Race with time
Ngày:2008-07-26
Thời gian chạy:0.100s-0.300s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:VNOI Marathon '08 - Round 7/DivA
Problem Setter: Phạm Lê Quang

hide comments
2021-08-25 08:11:09
Mọi người cho em hỏi , em đang thắc mắc ở chỗ màu sơn phòng của các bạn của Harry . Cho em hỏi cho màu sơn ở các phòng đó để làm gì , Với cả mong author xem lại chỗ màu sơn này , vì ở bạn số 2 , tọa độ (2 ; 1 ) ban đầu là màu 1 mà sao phòng bạn ấy lại là màu 2 ạ , Em cảm ơn !! Mong Author phản hồi em sớm ạ

Last edit: 2021-08-25 08:15:33
2014-07-23 11:54:57 Phạm Trung Hiếu
con lon goi tinh
2012-09-22 15:41:56 Shinken Yellow
?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.