Jury Meeting
Contest: Codeforces Round 433 (Div. 1, based on Olympiad of Metropolises)
Difficulty rating: 1800
Tags: greedy, sortings, two pointers

Country of Metropolia is holding Olympiad of Metrpolises soon. It mean that all jury members of the olympiad should meet together in Metropolis (the capital of the country) for the problem preparation process.

There are n + 1 cities consecutively numbered from 0 to n. City 0 is Metropolis that is the meeting point for all jury members. For each city from 1 to n there is exactly one jury member living there. Olympiad preparation is a long and demanding process that requires k days of work. For all of these k days each of the n jury members should be present in Metropolis to be able to work on problems.

You know the flight schedule in the country (jury members consider themselves important enough to only use flights for transportation). All flights in Metropolia are either going to Metropolis or out of Metropolis. There are no night flights in Metropolia, or in the other words, plane always takes off at the same day it arrives. On his arrival day and departure day jury member is not able to discuss the olympiad. All flights in Megapolia depart and arrive at the same day.

Gather everybody for k days in the capital is a hard objective, doing that while spending the minimum possible money is even harder. Nevertheless, your task is to arrange the cheapest way to bring all of the jury members to Metrpolis, so that they can work together for k days and then send them back to their home cities. Cost of the arrangement is defined as a total cost of tickets for all used flights. It is allowed for jury member to stay in Metropolis for more than k days.

Input format:
The first line of input contains three integers n, m and k (1 ≤ n ≤ 105, 0 ≤ m ≤ 105, 1 ≤ k ≤ 106).

The i-th of the following m lines contains the description of the i-th flight defined by four integers di, fi, ti and ci (1 ≤ di ≤ 106, 0 ≤ fi ≤ n, 0 ≤ ti ≤ n, 1 ≤ ci ≤ 106, exactly one of fi and ti equals zero), the day of departure (and arrival), the departure city, the arrival city and the ticket cost.

Output format:
Output the only integer that is the minimum cost of gathering all jury members in city 0 for k days and then sending them back to their home cities.

If it is impossible to gather everybody in Metropolis for k days and then send them back to their home cities, output "-1" (without the quotes).

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
The optimal way to gather everybody in Metropolis in the first sample test is to use flights that take place on days 1, 2, 8 and 9. The only alternative option is to send jury member from second city back home on day 15, that would cost 2500 more.

In the second sample it is impossible to send jury member from city 2 back home from Metropolis.

Example input:
2 6 5
1 1 0 5000
3 2 0 5500
2 2 0 6000
15 0 2 9000
9 0 1 7000
8 0 2 6500

Example output:
24500

Example input:
2 4 5
1 2 0 5000
2 1 0 4500
2 1 0 3000
8 0 1 6000

Example output:
-1

Editorial:
Obviously, each member of the jury needs to buy exactly two tickets — to the capital and back.
Sort all flights by the day of departure. Now go through flights to the capital (forward flights) and one by one assume it is the last forward flight in answer (let's say it is scheduled on day d). Thus you are assuming that all forward flights are contained in some fixed prefix of flights. Make sure that there is at least one forward flight for every jury member in this prefix and find the cheapest forward flight among them for every person. All return flights we are interested in are contained in the suffix of flights list such that every flight's departure date is at least d + k + 1. Take similar steps: make sure that there is at least one return flight for every jury member in this suffix and find the cheapest return flight among them for every person as well. Select minimal cost among these variants or find out that the problem has no solution. Expected complexity: O(nm2) or O(m2 + n).
Just as the boundary of considered prefix moves right, the boundary of considered suffix moves right as well. This suggests that the problem could be solved by the two pointers method. Assume you are storing minimum forward flight's cost on current prefix (infinity if no flight exists) for every person, and you are storing multiset (ordered by cost) of all return flights on current suffix for each person as well. To proceed next prefix and conforming suffix do the following:
• Move prefix boundary to the next forward flight. If its cost ci is less than minimum forward flight's cost fwdfi from that city, then you could improve total cost: decrease it by ci - fwdfi and set fwdfi to ci since it's new minimal cost.
• Move suffix boundary to the next backward flight until there is such flight exists and it departure date difference with prefix boundary departure date is under k + 1.
• While moving suffix boundary, keep return flights multisets consistent: remove boundary flight right before moving that boundary to the next flight. Also check out if you are removing cheapest flight from multiset. If it is so, minimal flight cost for that city changed as well as total cost: it increases by difference between old minimal cost and new minimal cost. Keep in mind that if you are removing last flight from multiset, then there is no more appropriate return flight for this city and you should terminate the process.
Proceed these steps moving boundaries to the right until the process terminates. In this way you've reviewed the same prefixes and corresponding suffixes as in slower solution described above. Expected complexity: $${ \mathcal { O } } ( m \cdot \log m + n )$$.