{"raw_statement":[{"iden":"statement","content":"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.\n\nThere 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.\n\nYou 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.\n\nGather 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."},{"iden":"input","content":"The first line of input contains three integers _n_, _m_ and _k_ (1 ≤ _n_ ≤ 105, 0 ≤ _m_ ≤ 105, 1 ≤ _k_ ≤ 106).\n\nThe _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."},{"iden":"output","content":"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.\n\nIf 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)."},{"iden":"examples","content":"Input\n\n2 6 5\n1 1 0 5000\n3 2 0 5500\n2 2 0 6000\n15 0 2 9000\n9 0 1 7000\n8 0 2 6500\n\nOutput\n\n24500\n\nInput\n\n2 4 5\n1 2 0 5000\n2 1 0 4500\n2 1 0 3000\n8 0 1 6000\n\nOutput\n\n\\-1"},{"iden":"note","content":"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.\n\nIn the second sample it is impossible to send jury member from city 2 back home from Metropolis."}],"translated_statement":[{"iden":"statement","content":"Metropolia 国即将举办大都市奥林匹克竞赛。这意味着所有竞赛评审成员必须齐聚首都 Metropolis（该国的首都）进行题目准备工作。\n\n该国有 #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，以便共同工作。\n\n你了解该国的航班时刻表（评审成员认为自己足够重要，只使用航班出行）。Metropolia 的所有航班要么飞往 Metropolis，要么从 Metropolis 出发。该国没有夜航航班，换句话说，飞机总是在同一天起飞和到达。评审成员在抵达日和离开日无法参与竞赛讨论。Metropolia 的所有航班均在同一天起飞和到达。\n\n将所有人聚集在首都 #cf_span[k] 天是一项艰巨的任务，而在此过程中花费最少的钱则更加困难。然而，你的任务是安排一种最便宜的方式，将所有评审成员带到 Metropolis，使他们能够共同工作 #cf_span[k] 天，然后将他们送回各自的家乡城市。安排的成本定义为所有使用航班的机票总费用。允许评审成员在 Metropolis 停留超过 #cf_span[k] 天。\n\n输入的第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 105], #cf_span[0 ≤ m ≤ 105], #cf_span[1 ≤ k ≤ 106]）。\n\n接下来的 #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] 中恰好有一个为零），分别表示出发（和到达）日期、出发城市、到达城市和机票费用。\n\n请输出一个整数，表示将所有评审成员聚集在城市 #cf_span[0] 共同工作 #cf_span[k] 天，然后送他们返回各自家乡城市的最小总成本。如果无法在 Metropolis 集聚所有人 #cf_span[k] 天并送他们返回家乡，请输出 \"_-1_\"（不含引号）。\n\n在第一个样例测试中，将所有人聚集在 Metropolis 的最优方式是使用在第 #cf_span[1]、#cf_span[2]、#cf_span[8] 和 #cf_span[9] 天的航班。唯一的替代方案是让来自第二座城市的评审成员在第 #cf_span[15] 天返回家乡，这将多花费 2500。\n\n在第二个样例中，无法将来自城市 #cf_span[2] 的评审成员从 Metropolis 送回家乡。"},{"iden":"input","content":"输入的第一行包含三个整数 #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] 中恰好有一个为零），分别表示出发（和到达）日期、出发城市、到达城市和机票费用。"},{"iden":"output","content":"请输出一个整数，表示将所有评审成员聚集在城市 #cf_span[0] 共同工作 #cf_span[k] 天，然后送他们返回各自家乡城市的最小总成本。如果无法在 Metropolis 集聚所有人 #cf_span[k] 天并送他们返回家乡，请输出 \"_-1_\"（不含引号）。"},{"iden":"examples","content":"输入\n2 6 5\n1 1 0 5000\n3 2 0 5500\n2 2 0 6000\n15 0 2 9000\n9 0 1 7000\n8 0 2 6500\n输出\n24500\n\n输入\n2 4 5\n1 2 0 5000\n2 1 0 4500\n2 1 0 3000\n8 0 1 6000\n输出\n-1"},{"iden":"note","content":"在第一个样例测试中，将所有人聚集在 Metropolis 的最优方式是使用在第 #cf_span[1]、#cf_span[2]、#cf_span[8] 和 #cf_span[9] 天的航班。唯一的替代方案是让来自第二座城市的评审成员在第 #cf_span[15] 天返回家乡，这将多花费 2500。在第二个样例中，无法将来自城市 #cf_span[2] 的评审成员从 Metropolis 送回家乡。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\n- Let $ n $: number of non-capital cities (each with one jury member).\n- Let $ m $: number of flights.\n- Let $ k $: required number of consecutive days all jury members must be present in Metropolis (city 0).\n- Cities: $ 0 $ (Metropolis), $ 1 $ to $ n $ (home cities of jury members).\n- Each flight is a tuple $ (d, f, t, c) $: day of departure/arrival, departure city, arrival city, cost. Exactly one of $ f, t $ is 0.\n  - If $ f = 0 $: flight from Metropolis to city $ t $ (return flight).\n  - If $ t = 0 $: flight from city $ f $ to Metropolis (arrival flight).\n\n**Constraints:**\n\n- For each jury member in city $ i \\in \\{1, \\dots, n\\} $:\n  - Must arrive in Metropolis on some day $ a_i \\leq D $, where $ D $ is the start of the $ k $-day working period.\n  - Must depart from Metropolis on some day $ d_i \\geq D + k - 1 $, so that they are present on all days $ D, D+1, \\dots, D+k-1 $.\n  - Arrival and departure days do **not** count as working days.\n- Flights are only between Metropolis and one other city.\n- All flights occur on integer days $ d \\in [1, 10^6] $.\n\n**Objective:**\n\nMinimize total cost of flights such that:\n\n1. For each $ i \\in \\{1, \\dots, n\\} $, there exists:\n   - An arrival flight $ (a_i, i, 0, c_{\\text{in},i}) $ with $ a_i \\leq D $,\n   - A departure flight $ (d_i, 0, i, c_{\\text{out},i}) $ with $ d_i \\geq D + k - 1 $,\n2. The interval $ [D, D+k-1] $ is the same for all jury members (i.e., a common $ k $-day window of presence),\n3. $ D \\in \\mathbb{Z} $, $ D \\geq 1 $, $ D + k - 1 \\leq 10^6 $,\n4. For each $ i $, arrival and departure flights exist (otherwise, impossible).\n\n**Formal Problem:**\n\nLet:\n\n- $ A_i = \\{ (d, c) \\mid \\text{flight } (d, i, 0, c) \\text{ exists} \\} $: set of (arrival day, cost) pairs for jury member $ i $.\n- $ R_i = \\{ (d, c) \\mid \\text{flight } (d, 0, i, c) \\text{ exists} \\} $: set of (return day, cost) pairs for jury member $ i $.\n\nDefine:\n\n- $ \\text{min\\_in}_i(D) = \\min \\{ c \\mid (d, c) \\in A_i, d \\leq D \\} $, if such $ d $ exists; else $ \\infty $.\n- $ \\text{min\\_out}_i(D) = \\min \\{ c \\mid (d, c) \\in R_i, d \\geq D + k - 1 \\} $, if such $ d $ exists; else $ \\infty $.\n\nLet $ \\text{cost}(D) = \\sum_{i=1}^{n} \\left( \\text{min\\_in}_i(D) + \\text{min\\_out}_i(D) \\right) $.\n\n**Goal:**\n\n$$\n\\min_{D \\in \\mathbb{Z},\\ 1 \\leq D \\leq 10^6 - k + 1} \\text{cost}(D)\n$$\n\nIf for some $ i $, either $ A_i = \\emptyset $ or $ R_i = \\emptyset $, or for all $ D $, $ \\text{cost}(D) = \\infty $, output $ -1 $.\n\n**Note:** The function $ \\text{cost}(D) $ is piecewise constant and changes only at discrete flight days. Thus, only candidate values of $ D $ are those where $ D $ or $ D + k - 1 $ coincide with a flight day. However, since $ D $ can be any integer in range, we can precompute prefix minima for arrivals and suffix minima for departures over all possible days.\n\n**Efficient Computation:**\n\n- Precompute for each city $ i $:\n  - $ \\text{best\\_in}[d] = \\min \\{ c \\mid (d', c) \\in A_i, d' \\leq d \\} $ for $ d = 1 $ to $ \\max\\_day $.\n  - $ \\text{best\\_out}[d] = \\min \\{ c \\mid (d', c) \\in R_i, d' \\geq d \\} $ for $ d = 1 $ to $ \\max\\_day $.\n\nThen for each candidate $ D \\in [1, 10^6 - k + 1] $:\n\n$$\n\\text{cost}(D) = \\sum_{i=1}^{n} \\left( \\text{best\\_in}_i[D] + \\text{best\\_out}_i[D + k - 1] \\right)\n$$\n\nReturn minimum $ \\text{cost}(D) $ over all $ D $, or $ -1 $ if any $ \\text{best\\_in}_i[D] = \\infty $ or $ \\text{best\\_out}_i[D + k - 1] = \\infty $ for all $ D $.","simple_statement":null,"has_page_source":false}