2128: 拯救小Y行动

小Y被关在了一个N*M(M, N<=15)的迷宫中，迷宫里有不可逾越的墙和P种门(p<=10)。

从一个格子移动到另一个格子的时间是1，有些格子里有P种门的钥匙，拿所在格子钥匙的时间以及用钥匙开门的时间不计。

作为一个朋友，你的任务是用最少的时间救出小Y。 小Y在第N行第M列的位置，刚开始你在第一行第一列的位置。

第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。

然后1行是一个整数S，代表了钥匙的个数。

然后S行，每行3个数X,Y,Q，之间有一个空格分开，代表(X,Y)位置有一个开启Q门的钥匙。

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