Mountain trek
Hugo and Quido are planning a trek in the mountains.
There are various accomodation places for travellers in the mountains. Those may be trekking huts, shepherd cottages, astronomical observatories, tourist resorts, or other suitable spots. For simplicity reasons we will call each accomodation place a point. The points are connected with paths. The trekkers will travel along various paths and will always stay overnight at some point.
There are economic issues related to the trekking and the travellers ought to plan their trip visely. Some points may be costly to stay overnight, some paths may require paying for ferry or a bridge, hiring a guide and so on.
There are two values associated with each path: The length of the path in kilometers and the cost of the path.
It may happen that the traveller is forced by the weather or by other conditions to stay at a particular point for another night or for more nights. Therefore, two costs are associated with each point. The first cost expresses the price for staying overnight and the second expresses the price for staying at the point for a whole day between two consecutive nights. The second price applies only when the traveller does not travel along any paths at that particular day.
The terrain is difficult and each path is thus considered to be a one-direction path. There is always at most one path connecting any two points in each direction.
Hugo and Quido agreed upon the following strategy: They will start at the same day, each of them at a different point. Then they will travel separately along the paths until they meet at some point after a few days. They do not care too much which will be the meeting point or how long will the journey take. Their priority is to keep their shared spendings as low as possible. Another limiting factor are the distances. Hugo can walk each day at most HK kilometers and Quido can walk each day at most QK kilometers. If some paths between the points are short then each of them can pass by one or more points in the same day but no one can exceed his daily kilometers limit. They decided to plan their further common trekking only after they meet in the mountains, so this next part of their journey is not an important question for them now.
 Image 1. View of Haute Severaisse valley, French Southern Alps. Courtesy of Wikimedia Commons. |
The task
You are given a list of points and paths and all prices and distances associated with them.
Also, you are given the starting point and the daily kilometer limit of each trekker.
Compute the minimum total price of the trek. The total consists of both Hugo's and Quido's prices for
their respective treks. The total does not include the price for overnight accomodation
at the meeting point on the day they meet. All other prices are included.
Input
First line of input contains an integer N representing the number of points.
The points are labeled 0, 1, 2, ..., N−1.
Next, there are N lines, each line specifies all prices related to one point.
The lines are listed in ascending order of their corresponding point labels.
Each line starts with two integers representing the price of staying overnight and the price of
spending a whole day at that point without leaving it (in this order). These two values are followed by the number NP of
paths which begin at that point. Number NP is followed by exactly NP integer triplets, each triplet
corresponds to one path. The first number in the triplet is the label of the end point of the path.
The second number in the triplet is the length of the path in kilometers. The third number in the
triplet is the cost of traversing the path.
The last input line contains four integers. The first two represent Hugo's starting point and his daily
kilometers limit (in this order), the second two integers represent Quido's starting point and his daily
kilometers limit (also in this order).
All input values on one line are separated by one or more spaces.
None of the input values exceeds 500.
Output
Output contains one test line with one integer representing the minimum possible price of the trek. You may assume that there always exists a solution of the problem.
Example 1Input5 3 100 1 1 5 10 3 100 3 0 6 50 2 6 50 4 2 1 3 100 2 1 5 10 3 6 50 3 100 1 2 5 10 3 100 1 1 2 1 0 5 3 5Output 38The history of the trek is presented in the format [morning point] -> (price) -> [evening point] for both travellers at each day. The (price) term also includes the accomodation price for that particular day.
Day 1: H:[0] -> (13) -> [1] Q:[3] -> (13) -> [2] Day 2: H:[1] -> (2) -> [1] Q:[2] -> (10) -> [1] |
 Image 2. The travelling scheme corresponding to the input data of Example 1. The point prices are separated by slash and are listed in the same order as they are listed in the input. Each path is labeled first by its length and then by its price. All prices are underlined. |
Example 2Input8 10 400 1 1 20 5 10 400 1 2 20 5 10 400 1 3 20 5 10 400 1 4 20 5 10 400 1 5 20 5 10 400 1 6 20 5 10 400 1 7 20 5 10 400 1 0 20 5 0 45 7 22Output 225The history of the trek is presented in the format [morning point] -> (price) -> [evening point] for both travellers at each day. The (price) term also includes the accomodation price for that particular day.
Day 1: H:[0] -> (20) -> [2] Q:[7] -> (15) -> [0] Day 2: H:[2] -> (20) -> [4] Q:[0] -> (15) -> [1] Day 3: H:[4] -> (20) -> [6] Q:[1] -> (15) -> [2] Day 4: H:[6] -> (20) -> [0] Q:[2] -> (15) -> [3] Day 5: H:[0] -> (20) -> [2] Q:[3] -> (15) -> [4] Day 6: H:[2] -> (20) -> [4] Q:[4] -> (15) -> [5] Day 7: H:[4] -> (10) -> [6] Q:[5] -> (5) -> [6] |
 Image 3. The travelling scheme corresponding to the input data of Example 2. The point prices are separated by slash and are listed in the same order as they are listed in the input. Each path is labeled first by its length and then by its price. All prices are underlined. |
Example 3Input8 11 7 1 1 3 7 10 13 2 2 5 8 7 4 7 8 14 1 3 7 2 15 6 2 4 3 2 5 6 3 15 11 1 5 7 7 9 10 1 6 9 2 5 6 2 2 3 8 7 8 10 11 14 1 0 4 6 0 8 4 9Output 74The history of the trek is presented in the format [morning point] -> (price) -> [evening point] for both travellers at each day. The (price) term also includes the accomodation price for that particular day.
Day 1: H:[0] -> (18) -> [0] Q:[4] -> (16) -> [5] Day 2: H:[0] -> (17) -> [1] Q:[5] -> (7) -> [6] Day 3: H:[1] -> (8) -> [2] Q:[6] -> (8) -> [2] |
 Image 4. The travelling scheme corresponding to the input data of Example 3. The point prices are separated by slash and are listed in the same order as they are listed in the input. Each path is labeled first by its length and then by its price. All prices are underlined. |
Example 4
Input24 9 35 2 1 19 15 3 10 19 5 31 2 2 20 16 4 11 11 7 34 2 3 19 14 5 17 13 5 27 2 4 12 19 5 20 10 5 25 2 5 13 19 9 20 12 7 30 2 6 12 14 11 14 18 10 25 2 7 16 20 10 18 18 7 30 2 8 17 14 13 20 14 8 32 2 9 11 18 10 11 10 8 29 2 10 18 15 12 10 11 9 35 2 11 17 14 15 20 13 5 30 2 12 18 13 13 12 15 6 35 2 13 11 17 14 19 11 5 27 2 14 15 10 18 16 11 6 34 2 15 11 16 19 15 12 10 28 2 16 18 18 20 15 18 10 27 2 17 14 11 22 13 11 5 32 2 18 12 11 20 14 19 9 28 2 19 16 15 0 16 17 9 33 2 20 18 18 1 16 11 10 25 2 21 15 18 2 10 15 10 29 2 22 17 17 3 13 12 9 28 2 23 19 15 0 19 20 9 25 2 0 12 15 4 16 15 6 18 17 20Output
171The history of the trek is presented in the format
[morning point] -> (price) -> [evening point] for both travellers at each day.
The (price) term also includes the accomodation price for that particular day.
Day 1: H:[6] -> (27) -> [7] Q:[17] -> (29) -> [20] Day 2: H:[7] -> (22) -> [8] Q:[20] -> (22) -> [2] Day 3: H:[8] -> (19) -> [10] Q:[2] -> (20) -> [5] Day 4: H:[10] -> (14) -> [11] Q:[5] -> (18) -> [11]
Public data
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set