CF853B.Jury Meeting

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.

梅特罗波利亚国即将举办“大都市奥林匹克竞赛”。这意味着所有竞赛命题组成员需齐聚首都——大都市（Metropolis），共同参与试题命制工作。

全国共有 $n+1$ 座城市，编号从 $0$ 到 $n$ 依次排列。其中，城市 $0$ 即为首都大都市，是全体命题组成员的会合地点。对于编号从 $1$ 到 $n$ 的每座城市，恰好居住着一名命题组成员。命题工作是一项长期而繁重的任务，需连续进行 $k$ 天；在这全部 $k$ 天中，全部 $n$ 名命题组成员均须身处大都市，方可协同开展命题工作。

你已掌握该国的航班时刻表（命题组成员自视甚高，仅乘坐飞机出行）。梅特罗波利亚国内所有航班均为往返于大都市的单向航线：即所有航班要么飞往大都市，要么从大都市出发；不存在其他类型的航线。梅特罗波利亚没有夜航航班——换言之，飞机总是在抵达当日起飞。每位命题组成员在抵达当天及离开当天均无法参与命题讨论。此外，梅特罗波利亚所有航班的起飞与到达均发生在同一天。

在首都集结全部成员、确保其连续工作 $k$ 天，本已十分困难；若还要在此基础上使总花费最小化，则难度更甚。尽管如此，你的任务正是规划一种成本最低的方案：将所有命题组成员接至大都市，使其能共同工作满 $k$ 天，之后再将其送返各自家乡城市。本安排的总成本定义为所使用全部航班机票费用之和。允许命题组成员在大都市停留时间超过 $k$ 天。

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 d__i, f__i, t__i and c__i (1 ≤ d__i ≤ 106, 0 ≤ f__i ≤ n, 0 ≤ t__i ≤ n, 1 ≤ c__i ≤ 106, exactly one of f__i and t__i equals zero), the day of departure (and arrival), the departure city, the arrival city and the ticket cost.

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n \leq 10^5$，$0 \leq m \leq 10^5$，$1 \leq k \leq 10^6$）。

接下来的 $m$ 行中，第 $i$ 行描述第 $i$ 班航班，包含四个整数 $d_i$、$f_i$、$t_i$ 和 $c_i$（$1 \leq d_i \leq 10^6$，$0 \leq f_i \leq n$，$0 \leq t_i \leq n$，$1 \leq c_i \leq 10^6$，且 $f_i$ 与 $t_i$ 中恰好有一个等于 $0$），分别表示出发（及到达）日期、出发城市、到达城市和机票费用。

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).

输出将所有陪审团成员聚集到城市 0 并停留 k 天，然后再送回各自家乡城市的最小总成本（唯一整数）。

若无法在 Metropolis（即城市 0）将所有人聚集并停留 k 天，再送回各自家乡城市，则输出 \-1（不带引号）。

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.

第一个样例测试中，将所有人聚集到大都会市（Metropolis）的最优方案是使用第 1、2、8 和 9 天的航班。唯一的替代方案是让第二座城市的评委成员于第 15 天乘机返回家乡，但这将额外花费 2500。

第二个样例中，无法让第二座城市的评委成员从大都会市乘机返回家乡。