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
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.
## Output
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).
[samples]
## 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.
Metropolia 国即将举办大都市奥林匹克竞赛。这意味着所有竞赛评审成员必须齐聚首都 Metropolis（该国的首都）进行题目准备工作。
该国有 #cf_span[n + 1] 座城市，编号从 #cf_span[0] 到 #cf_span[n]。城市 #cf_span[0] 是 Metropolis，作为所有评审成员的集合地点。对于从 #cf_span[1] 到 #cf_span[n] 的每一座城市，恰好有一名评审成员居住于此。竞赛准备工作是一个漫长而艰巨的过程，需要 #cf_span[k] 天的工作时间。在这 #cf_span[k] 天内，所有 #cf_span[n] 名评审成员都必须在 Metropolis，以便共同参与题目工作。
你已知该国的航班时刻表（评审成员自认为足够重要，只使用航班出行）。Metropolia 的所有航班要么飞往 Metropolis，要么从 Metropolis 出发。该国没有夜航航班，换句话说，飞机总是在同一天起飞并抵达。评审成员在抵达日和离境日均无法参与竞赛讨论。Metropolia 的所有航班均在同一天起飞和抵达。
将所有人聚集在首都 #cf_span[k] 天是一项艰巨的目标，而在此过程中花费最少的钱则更加困难。但你的任务是安排一种最便宜的方式，将所有评审成员带到 Metropolis，使他们能够共同工作 #cf_span[k] 天，然后送他们返回各自的家乡城市。安排的成本定义为所有使用航班的票价总和。允许评审成员在 Metropolis 停留超过 #cf_span[k] 天。
输入的第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 105], #cf_span[0 ≤ m ≤ 105], #cf_span[1 ≤ k ≤ 106]）。
接下来的 #cf_span[m] 行中，第 #cf_span[i] 行描述了第 #cf_span[i] 个航班，包含四个整数 #cf_span[di], #cf_span[fi], #cf_span[ti] 和 #cf_span[ci]（#cf_span[1 ≤ di ≤ 106], #cf_span[0 ≤ fi ≤ n], #cf_span[0 ≤ ti ≤ n], #cf_span[1 ≤ ci ≤ 106]，且 #cf_span[fi] 和 #cf_span[ti] 中恰好有一个为 0），分别表示出发（和抵达）日期、出发城市、抵达城市和机票价格。
请输出一个整数，表示将所有评审成员聚集在城市 #cf_span[0] 共工作 #cf_span[k] 天，并将他们送回各自家乡城市的最小总成本。如果无法在 #cf_span[k] 天内将所有人聚集在 Metropolis 并送回各自城市，请输出 "_-1_"（不含引号）。
在第一个样例中，最优方案是使用在第 #cf_span[1]、#cf_span[2]、#cf_span[8] 和 #cf_span[9] 天的航班。唯一替代方案是让第二座城市的评审成员在第 #cf_span[15] 天返回，这将多花费 2500。
在第二个样例中，无法将城市 #cf_span[2] 的评审成员从 Metropolis 送回。
## Input
输入的第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 105], #cf_span[0 ≤ m ≤ 105], #cf_span[1 ≤ k ≤ 106]）。接下来的 #cf_span[m] 行中，第 #cf_span[i] 行描述了第 #cf_span[i] 个航班，包含四个整数 #cf_span[di], #cf_span[fi], #cf_span[ti] 和 #cf_span[ci]（#cf_span[1 ≤ di ≤ 106], #cf_span[0 ≤ fi ≤ n], #cf_span[0 ≤ ti ≤ n], #cf_span[1 ≤ ci ≤ 106]，且 #cf_span[fi] 和 #cf_span[ti] 中恰好有一个为 0），分别表示出发（和抵达）日期、出发城市、抵达城市和机票价格。
## Output
请输出一个整数，表示将所有评审成员聚集在城市 #cf_span[0] 共工作 #cf_span[k] 天，并将他们送回各自家乡城市的最小总成本。如果无法在 #cf_span[k] 天内将所有人聚集在 Metropolis 并送回各自城市，请输出 "_-1_"（不含引号）。
[samples]
## Note
在第一个样例中，最优方案是使用在第 #cf_span[1]、#cf_span[2]、#cf_span[8] 和 #cf_span[9] 天的航班。唯一替代方案是让第二座城市的评审成员在第 #cf_span[15] 天返回，这将多花费 2500。在第二个样例中，无法将城市 #cf_span[2] 的评审成员从 Metropolis 送回。
**Definitions:**
- Let $ n $: number of cities excluding Metropolis (cities $ 1 $ to $ n $), each with one jury member.
- Let $ m $: number of flights.
- Let $ k $: required number of consecutive days all jury members must be present in Metropolis (city 0).
- Metropolis is city $ 0 $.
- Each flight is a 4-tuple $ (d_i, f_i, t_i, c_i) $, where:
- $ d_i $: departure/arrival day (same day),
- $ f_i, t_i \in \{0, 1, \dots, n\} $, with exactly one of $ f_i, t_i = 0 $,
- $ c_i $: cost of flight.
- Flights are either:
- **Inbound**: $ f_i > 0, t_i = 0 $ (from city $ f_i $ to Metropolis),
- **Outbound**: $ f_i = 0, t_i > 0 $ (from Metropolis to city $ t_i $).
**Constraints:**
- Each jury member from city $ j \in \{1, \dots, n\} $ must:
- Arrive in Metropolis on some day $ a_j \leq D $,
- Depart from Metropolis on some day $ b_j \geq D + k $,
- Where $ D $ is the **start day** of the $ k $-day working period (to be chosen),
- So the working period is $ [D, D + k - 1] $, and all members must be present on **all** days in this interval.
- Arrival and departure days are **not** working days (i.e., jury member is not available on day $ a_j $ or $ b_j $).
- Thus, for each jury member $ j $:
- $ a_j \leq D - 1 $,
- $ b_j \geq D + k $.
**Objective:**
Minimize total cost:
$$
\sum_{j=1}^{n} \left( \text{cost of inbound flight for } j \text{ on day } a_j + \text{cost of outbound flight for } j \text{ on day } b_j \right)
$$
**Given:**
- Set $ F_{\text{in}} $: all inbound flights, indexed by $ i $, with $ t_i = 0 $, $ f_i = j $, cost $ c_i $, day $ d_i $.
- Set $ F_{\text{out}} $: all outbound flights, indexed by $ i $, with $ f_i = 0 $, $ t_i = j $, cost $ c_i $, day $ d_i $.
For each city $ j \in \{1, \dots, n\} $:
- Let $ \text{in}_j(d) = \min \{ c_i \mid (d_i, f_i, 0, c_i) \in F_{\text{in}}, f_i = j, d_i \leq d \} $, or $ \infty $ if no such flight exists.
- Let $ \text{out}_j(d) = \min \{ c_i \mid (d_i, 0, t_i, c_i) \in F_{\text{out}}, t_i = j, d_i \geq d \} $, or $ \infty $ if no such flight exists.
Define:
- $ \text{min\_in}[D] = \sum_{j=1}^{n} \text{in}_j(D - 1) $ — minimum cost to have all jury members arrive by day $ D - 1 $.
- $ \text{min\_out}[D] = \sum_{j=1}^{n} \text{out}_j(D + k) $ — minimum cost to have all jury members depart on or after day $ D + k $.
Then, for each possible start day $ D $ (from $ 1 $ to $ \max(\text{flight days}) - k $), compute:
$$
\text{total\_cost}(D) = \text{min\_in}[D] + \text{min\_out}[D]
$$
**Problem:**
Find:
$$
\min_{D \in \mathbb{Z}^+} \left\{ \text{total\_cost}(D) \right\}
$$
subject to:
- $ \text{min\_in}[D] < \infty $,
- $ \text{min\_out}[D] < \infty $,
- $ D \geq 1 $,
- $ D + k - 1 \leq \max(\text{flight days}) $.
If no such $ D $ exists, output $ -1 $.
**Note:** $ D $ must be chosen such that for every city $ j $, there exists an inbound flight arriving on or before $ D - 1 $, and an outbound flight departing on or after $ D + k $.