B – HURRY UP

B – Hurry Up!!

Problem

Air traveling may turn out to be a really nasty nightmare, if your bags get lost!

And the chances of your luggage getting lost seems to increase a lot if you have to change of flight operator many times during your trip.

Given a list of possible flights, find the cost of the cheaper trip, from a certain origin to a certain destination, that does not switch flight operators more than a given number of times. (Notice that the bound is on the number of times the flight operator changes while going through an airport, not the number of flight operators used in the trip).

Input

The first line of the input contains a single positive integer, indicating the number of airports. The second line of the input contains the maximum number of operators. The third line of the input contains a single positive integer, indicating the number of flight connections between airports. Then, a sequence of flight connections follows, one in each different line. Each flight connection is specified by four space-separated non-negative integers, in a single line. These integers indicate respectively the airport of origin, the destination airport, the cost of the trip, and the flight operator. You may assume that there will be no more than one flight connection between two given airports. You may also assume that no circular trips are possible. Finally, a line with three space-separated non-negative integers specifying the problem query: the airport of origin, the destination airport, and the maximum number of flight operator switches allowed. There will be no more than 150 airports.

Output

A line with a single integer, indicating the minimum cost of traveling between the airport of origin and the destination airport, not exceeding the specified number of switches of flight operators. If there is no possible path, respecting the flight operator switch limit, between the origin and destination, then your program should output impossible in a single line.

Sample Input 1

0 1 5 0

0 2 2 0

1 5 5 2

2 5 10 0

2 3 2 1

5 4 5 1

3 4 3 2

0 4 1

Sample Output 1

Sample Input 2