ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Dmitry Gozman Contest 1. Petrozavodsk training camp. Winter 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Bad Roads

Time limit: 2.0 second
Memory limit: 64 MB
In a country, there is a number of cities connected by unidirectional 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 f using no more than t minutes of time, no more than b standard units, find the minimal height of the bottom of the car which makes it possible.

Input

The first line of the input contains the number of cities n (1 ≤ n ≤ 100), the number of roads m (1 ≤ m ≤ 104), and the numbers of starting and ending cities s and f (1 ≤ s, f ≤ n). The second line contains numbers b (0 ≤ b ≤ 106) and t (0 ≤ t ≤ 106).
Each of the next m lines has the form ui vi ci ti hi. Here, ui is the starting city for i-th road, vi is the ending city, ci is 1 if it is a private road and 0 otherwise, ti is the time required to drive through that road, and hi is the height of the car required to pass (1 ≤ ui, vi ≤ n; 0 ≤ ti ≤ 104; 0 ≤ hi ≤ 106). All the numbers in the input are integers.

Output

If there is no way to drive from s to f 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 f; 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.

Samples

inputoutput
2 2 1 2
1 100
1 2 1 100 77
1 2 1 100 66
66
1
2
2 2 1 2
0 100
1 2 0 101 77
1 2 1 100 66
-1
Problem Author: Dmitry Gozman
Problem Source: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007
To submit the solution for this problem go to the Problem set: 1527. Bad Roads