Highway#3038

Highway

1 second

256 megabytes

Hard

The team from the Logarithmic region of Olympia is preparing for the Olympiad, which will be held in the distant city of Exponentialsk. The team will travel there in their own bus. The highway connecting the Logarithmic region to Exponentialsk consists of $N$ consecutive segments. For each segment, the team can choose the free road, which takes $a_{i}$ a_i seconds, or the toll road, which costs $c_{i}$ c_i Olympic cents and takes $b_{i}$ b_i seconds. Between the segments, there are interchanges that allow switching from one type of road to the other, taking $q_{i}$ q_i seconds regardless of the direction of the switch. Continuing on the same type of road incurs no delay. The journey can start on either the free or the toll road, and it can finish on either road of the last segment. Interchanges exist only between the $1$ st and $2$ nd segments, the $2$ nd and $3$ rd, ..., the $(N - 1)$ (N-1)th and $N$ th segment.

For the trip to the Olympiad, it is crucial to arrive on time, so the team is interested in the minimum cost to travel from the Logarithmic region to Exponentialsk in a total time not exceeding $T$ seconds. On the return trip, the time is not critical, and the team aims to pay no more than $S$ Olympic cents for tolls. All travel times and tolls are the same in both directions.

Write a program that, using the information about the free and toll roads, will determine:

The minimum cost to reach the Olympiad within $T$ seconds;
The minimum time to return from the Olympiad while paying no more than $S$ cents in tolls.

Input

The first line contains three integers: $N$ ( $2 \leq N \leq 40$ 2 \le N \le 40) — the number of highway segments, $T$ ( $0 \leq T \leq 1 0^{16}$ 0 \le T \le 10^{16}) — the time limit for the first question, and $S$ ( $0 \leq S \leq 1 0^{16}$ 0 \le S \le 10^{16}) — the cost limit for the second. The second line contains three integers $a_{1}$ a_1, $b_{1}$ b_1, and $c_{1}$ c_1 — the time to travel on the free and toll roads of the first segment, and the cost for the toll road. Each of the next $N - 1$ N-1 lines contains four integers $q_{i}$ q_i, $a_{i}$ a_i, $b_{i}$ b_i, and $c_{i}$ c_i — the time for switching between roads, then the time to travel on the free and toll roads of this segment, and the toll cost. On the way to the Olympiad, $q_{i}$ q_i is the time required to switch from the $(i - 1)$ (i-1)th to the $i$ th segment, and for the return trip, $q_{i}$ q_i is the time required to switch from the $i$ th to the $(i - 1)$ (i-1)th segment (if the bus moves from the toll road to the free road, or vice versa). All $a_{i}$ a_i, $b_{i}$ b_i, and $c_{i}$ c_i ( $1 \leq i \leq N$ 1 \le i \le N) are integers from $1$ to $1 0^{15}$ 10^{15}. All $q_{i}$ q_i ( $2 \leq i \leq N$ 2 \le i \le N) are integers from $0$ to $1 0^{9}$ 10^9.

Output

Output a single line containing two integers: the minimum cost to reach the Olympiad within $T$ seconds, and the minimum time to return from the Olympiad while paying no more than $S$ Olympic cents in tolls. If no such way exists, output $- 1$ for that value.

Examples

Example 1

Note

Explanation: The cheapest way within $2012$ seconds is to travel the first segment on the toll road, then on the free road: total cost $10000 + 0 + 0 + 0 + 0 = 10000$ 10000 + 0 + 0 + 0 + 0 = 10000 in time $17 + 4$ 17 + 4 (switch) $+ 1000 + 100 + 10 + 1 = 1132$ + 1000 + 100 + 10 + 1 = 1132. The fastest way to return with tolls not exceeding $2012$ is the $5$ th and $4$ th segments on the free road, $3$ rd and $2$ nd on the toll road, $1$ st on the free road: time $1 + 10 + 2$ 1 + 10 + 2 (switch) $+ 17 + 17 + 4$ + 17 + 17 + 4 (switch) $+ 10000 = 10051$ + 10000 = 10051 with tolls $0 + 1000 + 100 + 0 + 0 = 1100$ 0 + 1000 + 100 + 0 + 0 = 1100.