Northern Hike
Quido is working for an outdoor activities company.
He has to organize a hike in the remote Swedish countryside.
The hike will follow one long trail in the mountains, in a given direction. Hikers never walk back on the trail and they do not traverse any
part of thee trail more than once. Previously, many checkpoints were estabilished on the trail.
Some of the checkpoints also serve as camp sites.
A hike is divided into some number of consecutive sections. Each section of a hike starts and ends on a camp site.
When a section ends on a particular camp site the next section starts on the same camp site.
Three numeric parameters are known for each checkpoint:
The elevation (altitude above the sea level) of the check point, the distance to the next checkpoint, the time it takes to get on foot to the next check point.
There are many factors Quido has to take into account in his planning.
Each hike section is limited by a set of carefully chosen parameters. They are called one section limits.
There is a minimum and a maximum distance hikers can walk in each section.
There is a minimum and a maximum time hikers can spend walking in each section.
There is a minimum and a maximum uphill elevation difference hikers can climb in each section.
Each next checkpoint on the track is either downhill or uphill from the previous one.
The uphill elevation difference of a part of the trail is the sum of all elevation differences between
two consecutive checkpoints in that part of the trail, such that the second checkpoint is uphill from the first one.
The downhill elevation differences are not considered at all during the hike.
A hike section always is maximal, in the sense that when a start camp site of a section is given
the end camp of the section is chosen in such way that it is the most distant camp site from the start one
and simultaneously its choice does not violate one section limits.
It is obvious that different hikes may be planned according to the given limits.
Another set of limits, so called hike limits, are also specified.
There is a minimum and a maximum distance traveled in the entire hike.
There is also a minimum and a maximum total uphill elevation difference climbed in the entire hike.
With the given limits, Quido has to find the best hike.
Two hikes are compared as follows:
The hike which has more total distance travelled is the better one.
When two hikes cover the same distances the better one is that one in which the total uphill elevation difference is bigger.
When two hikes are equal in both the total distance and the total uphill elevation difference the better one is that one
which consists of smaller number of sections.
 Image 1. A profile of a trail. The distances are written in brown below the lines connecting the checkpoints, the times are written above the lines. The camp sites are marked by squares. The checkpoints in the image are labeled 1 to 16 to to be easily discerned. The image depicts Example 1 below. |
The task
You are given a sequence of checkpoints and their parameters. Also, you are given one section limits and hike limits. Find the best hike.
Input
The first input line contains six non-negative integers, separated by spaces, representing one section limits.
They are, in this order, the minimum and the maximum distance, the minimum and the maximum time, the minimum and the maximum
uphill elevation difference.
The second input line contains four non-negative integers separated by spaces, representing hike limits.
They are, in this order, the minimum and the maximum distance, the minimum and the maximum total uphill elevation difference.
The third input line contains one integer N, the number of checkpoints on the trail.
Next there are N lines each of which represents one checkpoint. The checkpoints are listed in the same order as they appear on the trail
in the direction of the hike.
Each line contains four values C, E, D, T separated by spaces.
C is 0 or 1. Value 0 indicates the checkpoint is not a camp site, value 1 indicates the checkpoint is a camp site.
Values E, D, T represent the elevation of the checkpoint, the distance to the next checkpoint and the
time to get to the next checkpoint, respectively.
It holds, 2 ≤ N ≤ 105. All other input values are non-negative and less than 104.
Output
The output contains one text line with three integers separated by space, representing the total distance, the total total uphill elevation difference and the number of sections in the best hike. The data guarantee that there is always at least one hike satisfying all given limits.
Example 1
Input10 40 10 40 100 500 10 50 100 800 16 0 200 10 3 1 400 8 4 1 200 12 5 0 500 6 2 1 400 7 3 1 100 10 6 0 300 12 5 1 500 2 1 1 400 8 3 0 600 8 5 0 900 12 5 1 500 4 1 0 400 4 2 1 200 15 7 0 300 10 3 0 200 0 0Output
49 700 2The data of Example 1 are depicted in Image 1. The best hike starts at checkpoint 3, ends in checkpoint 9, and it consists of two sections, the first is from checkopint 3 to checkpoint 6, the second one is from checkopint 6 to checkpoint 9.
Example 2
Input5 9 20 50 100 200 10 80 300 500 14 0 100 5 11 1 50 2 10 0 200 2 11 0 150 2 10 1 100 2 11 1 50 2 10 0 200 2 11 0 150 2 10 1 100 2 11 1 50 4 10 1 200 3 11 0 150 2 10 0 100 1 11 1 250 0 0Output
20 450 3Presume the checkpoints are labeled 1 to 14. The best hike consists of three sections, their respective starts are at checkpoints 5, 9, 11. The hike ends at checkpoint 14.
Example 3
Input10 200 10 90 100 1100 30 45 50 1000 11 1 600 20 10 0 800 18 9 1 600 16 8 0 800 14 7 1 600 13 6 0 800 10 5 1 600 10 5 0 800 12 6 1 600 14 7 0 800 16 90 1 600 0 0Output
45 400 1Presume the checkpoints are labeled 1 to 11. The best hike consists of a single section from checkpoint 5 to checkopint 9.
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