eolymp
bolt
Try our new interface for solving problems
Problems

Bad Roads

Bad Roads

Time limit 2 seconds
Memory limit 64 MiB

In a country, there is a number of cities connected by roads. Due to insufficient budget, some roads are covered with pot-holes, so certain cars cannot use certain roads. Thus each road has the height number associated with it — that is the minimal height of the bottom of a car that can drive through that road. On the other hand, some roads are private, and one should pay for using them. Luckily, the amount to be paid is standartized and equals one standard unit. Finally, for each road, the time required to drive through it is known.

Given that you have to drive from city s to city t using no more than maxtime minutes of time, no more than money standard units, find the minimal height of the bottom of the car which makes it possible.

Input data

The number of cities n (1n100), the number of roads m (1m10^4), and the numbers of starting and ending cities s and t (1s, tn) are given on the first line of the input. The second line contains money (0money10^6) and maxtime (0maxtime10^6).

Each of the next m lines has the form u_i v_i c_i t_i h_i. Here, u_i is the starting city for i-th road, v_i is the ending city, c_i is 1 if it is a private road and 0 otherwise, t_i is the time required to drive through that road, and h_i is the height of the car required to pass (1u_i, v_in, 0t_i10^4 and 0h_i10^6). Note that the roads are unidirectional. All the numbers in the input are integers.

Output data

If there is no way to drive from s to t under given restrictions, output "-1". Otherwise write on the first line the minimal height of the car; the second line should contain the number of roads used to travel from s to t; and the third line must be filled by the numbers of the roads you used in the order of usage. Roads are numbered from 1 to m; the order is the same as in input.

Examples

Input example #1
2 2 1 2
1 100
1 2 1 100 77
1 2 1 100 66
Output example #1
66
1
2
Author Dmitry Gozman
Source Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007