Olympiad in Informatics

Harry Potter và mê cung tử thần

Trong chuyến phiêu lưu tìm kiếm những bảo bối tử thần, Harry cùng các bạn của cậu đã lạc vào một mê cung bí mật. Ngay khi họ vừa bước chân vào, các bức tường lập tức mọc lên bốn phía, chia mê cung thành N*N phòng có kích thước 1*1 và nhóm của Harry bị nhốt trong một số phòng. Mỗi phòng đều có 4 cánh cửa, mỗi chiếc nằm trên 1 bức tường của phòng đó.

Các con quái vật chỉ xuất hiện trong các phòng có Harry và các bạn của cậu. Số quái vật ở một phòng luôn luôn bằng số người trong phòng. Điều này có nghĩa là khi 1 người di chuyển từ phòng X sang phòng Y, thì ở phòng Y sẽ có thêm 1 con quái vật.

Để sống sót, buộc Harry và các bạn phải chiến đấu với lũ quái vật và tìm đường thoát ra ngoài. Thời gian để tiêu diệt 1 con quái vật ở phòng (I, J) là A[I, J]. (Đánh số các phòng từ trái sang phải, từ trên xuống dưới). Một người chỉ có thể cùng 1 lúc chiến đấu với 1 con quái vật, và bắt buộc phải tiêu diệt xong quái vật đó mới có thể chuyển sang phòng khác.

Nhờ tấm bản đồ đạo tặc, Harry biết được những người bạn của mình đang ở phòng nào. Cậu cũng phát hiện ra rằng, mỗi phòng nhốt bạn mình đều được sơn bằng một màu riêng biệt, và các cánh cửa nằm trên 4 bức tường bao ngoài của mê cung cũng có nhiều màu sắc khác nhau. Bây giờ cậu cần phải hướng dẫn từng người chạy tới cánh cửa cùng màu với phòng nhốt người đó. Nhưng khi có một người thoát ra ngoài mê cung, thì ngay lập tức, quái vật trong mê cung sẽ hồi phục lại sức mạnh như ban đầu, và 4 bức tường của căn phòng bí mật sẽ quay 1 đơn vị theo chiều kim đồng hồ, làm các cánh cửa màu trên đó cũng quay theo. Hay nói cách khác, nếu ta đi dọc theo 4 bức tường của căn phòng bí mật theo chiều kim đồng hồ thì mỗi cánh cửa mà ta đi tới sẽ đổi sang màu cũ của cánh cửa ngay phía sau ta (Xem hình vẽ).

Do tình thế khó khăn nên chỉ khi một người thoát khỏi mê cung thì Harry mới hướng dẫn người tiếp theo. Bạn hãy giúp Harry hướng dẫn cho tất cả các bạn của mình thoát khỏi mê cung trong thời gian ngắn nhất!

(P/s: Nếu bạn hỏi Harry hướng dẫn cho các bạn mình bằng cách nào? Cậu ấy dùng thần chú “Sonorus!” (Âm vang) làm giọng nói của mình vang vọng khắp mê cung. :D)

Dữ liệu

Dòng đầu ghi 2 số nguyên dương N, K. Với N là kích thước của mê cung, K là số người trong nhóm bạn của Harry.

Trong I dòng tiếp theo, mỗi dòng ghi J số nguyên không âm. Số thứ J trên dòng I là A[I, J] thể hiện thời gian cần thiết để tiêu diệt quái vật trong phòng (I, J).

Trong K dòng tiếp, mỗi dòng ghi 1 bộ 3 số nguyên không âm I, J, C. Bộ số (I, J, C) trên dòng thứ X thể hiện rằng người bạn thứ X đang ở phòng (I, J) và phòng này được sơn màu C.

Dòng cuối cùng ghi 4*N số nguyên không âm, là màu của các cánh cửa trên 4 bức tường bao quanh mê cung, lần lượt theo chiều kim đồng hồ, bắt đầu từ cánh cửa ở bức tường phía trên của phòng nhỏ (1,1). (Thứ tự giống như trong hình 1)

Kết quả

Một số nguyên duy nhất là thời gian nhỏ nhất để tất cả mọi người trong nhóm bạn của Harry có thể thoát khỏi mê cung.

Giới hạn

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

Ví dụ

Dữ liệu:
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

Kết quả:
3