A skiing competition is taking place. There are points on the hill and trails to get from one to another. It takes seconds to get from point to (and back) on the trail. It takes the same amount of time to get back on the same trail. The competition starts from and goes to . There are competitors racing. Due to rigging of the race, the competitor will take the fastest path. Two paths are identical in rank if they take the same amount of time. A competitor may not go back to a previously visited point.
To prepare the competitors, you will provide each of them with two pieces of information, the time they will take to finish the race, and the minimum time they will spend on one trail.
The first line will contain, , all space separated.
The next lines will contain three integers, and meaning a trail from to (and vice versa) will take units of time to ski.
The next lines will contain a single integer, , the designated path that the competitor will take.
For all subtasks: , and
For subtasks 1 and 2:
For subtasks 3 and 4:
Subtask 1 : and
Subtask 2 : and
Subtask 3 : and
Subtask 4 : and
lines containing two integers, the time it will take this competitor to finish the race, and the fastest time this competitor can take to get from one point to another. If there are no more paths, output
-1 for that query.
5 8 1 5 4 1 2 1 1 3 2 2 3 3 3 4 2 3 5 3 2 4 1 4 5 1 1 5 5 1 2 3 4
3 1 5 1 7 1 -1
Explanation for Sample Output
The trails look like the following:
The fastest path is
The second fastest path is
The third fastest (slowest) path is
A fourth path doesn't exist.
The fastest trail on all these paths is unit of time.