2481: 救援行动

    一切危险都结束了。Atlantis人在King的带领下来到了新的新的大陆，并且来到了一个奇怪的地方(今江苏南京)。这里的土著人对他们似乎不是很友好(中国以前也有土著？！)，在短暂的交涉以后，他们把King抓了起来，并且放到了一个迷宫当中。     土著人比Atlantis岛上的奇怪生物明智多了，他们把King关在了一个N*M(M, N<=15)的迷宫中(制作成本高了，迷宫就小了……)，迷宫里有不可逾越的墙和P种门(p<=10)。从一个格子移动到另一个的时间是1，拿所在格子的钥匙的时间以及用钥匙开门的时间不计。你的任务是用最少的时间救出King。

    第1行3个整数，表示N，M，P的值。     第2行1个整数K，表示迷宫中门的墙的总个数。     以后K行，每行5个数，分别为X1,Y1,X2,Y2和G。     G>0时，代表(X1,Y1)->(X2,Y2)有一个G类的门。     G=0时，代表(X1,Y1)->(X2,Y2)有一个墙，其中|X1-X2|+|Y1-Y2|=1。     然后是一个整数S，代表了钥匙的个数     然后S行，每行3个数，X,Y,Q，代表(X,Y)位置有一个开启Q门的钥匙。

    包含一个整数，代表救出King的最少时间，若不能救出，则输出“Poor King!”

4 4 9
9
1 2 1 3 2
1 2 2 2 0
2 1 2 2 0
2 1 3 1 0
2 3 3 3 0
2 4 3 4 1
3 2 3 3 0
3 3 4 3 0
4 3 4 4 0
2
2 1 2
4 2 1

14