PROGRAMMING:Island Rescue
In 1944, special forces Mike received an order from the Ministry of defense to rush to an island in the Pacific Ocean immediately to rescue Private Ryan, who was captured by the enemy. Ryan was imprisoned in a maze with complex terrain. Fortunately, Mike got the map of the maze. The shape of the maze is a rectangle,
Its north-south direction is divided into $$n $$rows, east-west direction is divided into $$M $$columns, so the whole maze is divided into $$n times M $$units. The position of each cell can be represented by an ordinal number pair (cell row number, cell column number). The two adjacent units in North-South or East-West directions may be interconnected, or there may be a locked door or an insurmountable wall. There are some units in the maze that store keys, and all the doors are divided into $$p $$classes. The keys to open the same class of doors are the same, and the keys to different classes of doors are different.
Private Ryan was held in the southeast corner of the labyrinth, the unit of $$\ left (n, m, right) $, and was unconscious. There's only one entrance to the maze, in the northwest corner. That is to say, Mike can go directly to the $$- left (1,1-right) $$unit. In addition, the time for Mike to move from one unit to another adjacent unit is $$1 $. The time for taking the key of the unit and opening the door with the key can be ignored.
Try to design an algorithm to help Mike reach Ryan's unit in the fastest way and rescue Private Ryan.
###Input format:
The first line has three integers representing the values of $$n, m, p $.
The second line is an integer $$k $, representing the total number of doors and walls in the maze.
In line $$I + 2 $$, $$left (1 / Leq I / Leq K / right) $$, there are $$5 $$integers,
The order is $$X_{ i1},y_{ i1},x_{ i2},y_{ i2},g_{ i} $$: when $$g_{ i} When $$GEQ 1 $, it means $$left (x)_{ i1},y_{ I1} (right) $$unit
And $$\ left (x_{ i2},y_{ I2} (right) $$there is a second grid between units_{ i} The door of the $$class, when $$g_{ i} When = 0 $$, the table
Show $$\ left (x)_{ i1},y_{ I1} (right) $$unit and $$\ left (x)_{ i2},y_{ There is an insurmountable wall between the cells.
Line $$K + 3 $$is an integer $$s $, which represents the total number of keys stored in the maze.
The $$K + 3 + J $$line is $$left (1 / Leq J / Leq s / right) $, with $$3 $$integers, followed by $$X_{ i1},y_{ i1},q_{ i} $$, which means that the $$J $$key is stored in $$\ left (x)_{ i1},y_{ I1} (right) $$unit, and the $$J $$key is used to open the $$Q_{ i} $$class gate.
The adjacent integers in the same row of input data are separated by a space.
Data guaranteed
$$ \left| x_{ i1} - x_{ i2} \right| + \left| y_{ i1} - y_{ i2} \right| = 1,0 \leq g_{ i} \leq p $$
$$ 1 \leq q_{ i} \leq p $$
$$ n,m,p \leq 10,k < 150 $$
###Output format:
Output the shortest time for Mike to rescue Private Ryan. If there is no solution to the problem, $- 1 $$.
###Input example:
Here is a set of inputs. For example:
```in
4 4 9
nine
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
two
2 1 2
4 2 1
```
###Output example:
The corresponding output is given here. For example:
```out
fourteen
```
answer：If there is no answer, please comment
Its north-south direction is divided into $$n $$rows, east-west direction is divided into $$M $$columns, so the whole maze is divided into $$n times M $$units. The position of each cell can be represented by an ordinal number pair (cell row number, cell column number). The two adjacent units in North-South or East-West directions may be interconnected, or there may be a locked door or an insurmountable wall. There are some units in the maze that store keys, and all the doors are divided into $$p $$classes. The keys to open the same class of doors are the same, and the keys to different classes of doors are different.
Private Ryan was held in the southeast corner of the labyrinth, the unit of $$\ left (n, m, right) $, and was unconscious. There's only one entrance to the maze, in the northwest corner. That is to say, Mike can go directly to the $$- left (1,1-right) $$unit. In addition, the time for Mike to move from one unit to another adjacent unit is $$1 $. The time for taking the key of the unit and opening the door with the key can be ignored.
Try to design an algorithm to help Mike reach Ryan's unit in the fastest way and rescue Private Ryan.
###Input format:
The first line has three integers representing the values of $$n, m, p $.
The second line is an integer $$k $, representing the total number of doors and walls in the maze.
In line $$I + 2 $$, $$left (1 / Leq I / Leq K / right) $$, there are $$5 $$integers,
The order is $$X_{ i1},y_{ i1},x_{ i2},y_{ i2},g_{ i} $$: when $$g_{ i} When $$GEQ 1 $, it means $$left (x)_{ i1},y_{ I1} (right) $$unit
And $$\ left (x_{ i2},y_{ I2} (right) $$there is a second grid between units_{ i} The door of the $$class, when $$g_{ i} When = 0 $$, the table
Show $$\ left (x)_{ i1},y_{ I1} (right) $$unit and $$\ left (x)_{ i2},y_{ There is an insurmountable wall between the cells.
Line $$K + 3 $$is an integer $$s $, which represents the total number of keys stored in the maze.
The $$K + 3 + J $$line is $$left (1 / Leq J / Leq s / right) $, with $$3 $$integers, followed by $$X_{ i1},y_{ i1},q_{ i} $$, which means that the $$J $$key is stored in $$\ left (x)_{ i1},y_{ I1} (right) $$unit, and the $$J $$key is used to open the $$Q_{ i} $$class gate.
The adjacent integers in the same row of input data are separated by a space.
Data guaranteed
$$ \left| x_{ i1} - x_{ i2} \right| + \left| y_{ i1} - y_{ i2} \right| = 1,0 \leq g_{ i} \leq p $$
$$ 1 \leq q_{ i} \leq p $$
$$ n,m,p \leq 10,k < 150 $$
###Output format:
Output the shortest time for Mike to rescue Private Ryan. If there is no solution to the problem, $- 1 $$.
###Input example:
Here is a set of inputs. For example:
```in
4 4 9
nine
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
two
2 1 2
4 2 1
```
###Output example:
The corresponding output is given here. For example:
```out
fourteen
```
answer：If there is no answer, please comment