Highway
The team from the Logarithmic region of Olympia is gearing up for the Olympiad, which will be held in the distant city of Exponentialsk. They will be traveling in their own bus. The highway connecting the Logarithmic region to Exponentialsk is divided into N consecutive segments. For each segment, the team can choose between a free road, which takes a_i seconds, or a toll road, which costs c_i Olympic cents and takes b_i seconds. Between these segments, there are interchanges where the team can switch from one type of road to the other, taking q_i seconds to do so (this time is the same whether switching from toll to free or vice versa). Continuing on the same type of road does not incur any switching time. The journey can start on either the free or toll road, and it can end on either road in the last segment. Interchanges are only present between the 1st and 2nd segments, the 2nd and 3rd, and so on, up to the (N–1)-th and N-th segments.
For the trip to the Olympiad, it is crucial to arrive on time, so the team is interested in finding the minimum cost to travel from the Logarithmic region to Exponentialsk, while spending no more than T seconds in total. On the return trip, time is less critical, and the team aims to spend no more than S Olympic cents on tolls. The time and toll costs are identical in both directions.
Write a program that, using the data about the free and toll roads on the highway, will determine:
The minimum cost to reach the Olympiad within T seconds;
The minimum time to return from the Olympiad, spending no more than S cents on tolls.
Input
The first line contains three integers: N (2 ≤ N ≤ 40) - the number of highway segments, T (0 ≤ T ≤ 10^16) - the time limit for the first task, and S (0 ≤ S ≤ 10^16) - the cost limit for the second task. The second line contains three integers a_1, b_1, and c_1 - the time to travel on the free and toll roads of the 1st segment, and the toll cost. Each of the following N – 1 lines contains four integers q_i, a_i, b_i, and c_i - first the time for switching between roads, then the time to travel on the free and toll roads of this segment, and finally the toll cost. Note that on the way to the Olympiad, q_i is the time needed to switch from the (i–1)-th segment to the i-th, and on the return trip, q_i is the time needed to switch from the i-th segment to the (i–1)-th (assuming the bus switches from toll to free or vice versa). All values a_i, b_i, and c_i (1 ≤ i ≤ N) are within the range from 1 to 10^15. All values q_i (2 ≤ i ≤ N) are within the range from 0 to 10^9.
Output
The output should be a single line containing two integers: the cost of the cheapest way to reach the Olympiad within T seconds, and the duration of the fastest way to return from the Olympiad, spending no more than S cents on tolls. If no such way exists, output -1 for that particular value.
Explanation: The cheapest way within 2012 seconds is to travel the 1st segment on the toll road, then on the free road: total cost 10000 + 0 + 0 + 0 + 0 = 10000 in time 17 + 4 (switching) + 1000 + 100 + 10 + 1 = 1132. The fastest way to return with tolls not exceeding 2012 is the 5th and 4th segments on the free road, 3rd and 2nd on the toll road, 1st on the free road: time 1 + 10 + 2 (switching) + 17 + 17 + 4 (switching) + 10000 = 10051 with tolls 0 + 1000 + 100 + 0 + 0 = 1100.