C. Hacker, pack your bags!

Codeforces

IDCF822C

Time2000ms

Memory256MB

Difficulty—

binary searchgreedyimplementationsortings

English · Original

Chinese · Translation

Formal · Original

It's well known that the best way to distract from something is to do one's favourite thing. Job is such a thing for Leha. So the hacker began to work hard in order to get rid of boredom. It means that Leha began to hack computers all over the world. For such zeal boss gave the hacker a vacation of exactly _x_ days. You know the majority of people prefer to go somewhere for a vacation, so Leha immediately went to the travel agency. There he found out that _n_ vouchers left. _i_\-th voucher is characterized by three integers _l__i_, _r__i_, _cost__i_ — day of departure from Vičkopolis, day of arriving back in Vičkopolis and cost of the voucher correspondingly. The duration of the _i_\-th voucher is a value _r__i_ - _l__i_ + 1. At the same time Leha wants to split his own vocation into two parts. Besides he wants to spend as little money as possible. Formally Leha wants to choose exactly two vouchers _i_ and _j_ (_i_ ≠ _j_) so that they don't intersect, sum of their durations is **exactly** _x_ and their total cost is as minimal as possible. Two vouchers _i_ and _j_ don't intersect if only at least one of the following conditions is fulfilled: _r__i_ < _l__j_ or _r__j_ < _l__i_. Help Leha to choose the necessary vouchers! ## Input The first line contains two integers _n_ and _x_ (2 ≤ _n_, _x_ ≤ 2·105) — the number of vouchers in the travel agency and the duration of Leha's vacation correspondingly. Each of the next _n_ lines contains three integers _l__i_, _r__i_ and _cost__i_ (1 ≤ _l__i_ ≤ _r__i_ ≤ 2·105, 1 ≤ _cost__i_ ≤ 109) — description of the voucher. ## Output Print a single integer — a minimal amount of money that Leha will spend, or print - 1 if it's impossible to choose two disjoint vouchers with the total duration **exactly** _x_. [samples] ## Note In the first sample Leha should choose first and third vouchers. Hereupon the total duration will be equal to (3 - 1 + 1) + (6 - 5 + 1) = 5 and the total cost will be 4 + 1 = 5. In the second sample the duration of each voucher is 3 therefore it's impossible to choose two vouchers with the total duration equal to 2.

[{"iden":"statement","content":"众所周知，分散注意力的最佳方式就是做自己最喜欢的事情。对Leha来说，编程就是这样的事情。\n\n于是，这位黑客开始努力工作以摆脱无聊。这意味着Leha开始在全球范围内黑入计算机。为了表彰这种热情，老板给了黑客整整 #cf_span[x] 天的假期。众所周知，大多数人喜欢外出度假，因此Leha立即去了旅行社。在那里，他发现还剩下 #cf_span[n] 份度假券。第 #cf_span[i] 份度假券由三个整数 #cf_span[li]、#cf_span[ri]、#cf_span[costi] 描述，分别表示从Vičkopolis出发的日期、返回Vičkopolis的日期以及该度假券的价格。第 #cf_span[i] 份度假券的持续时间为 #cf_span[ri - li + 1]。\n\n与此同时，Leha希望将自己的假期分成两部分。此外，他还希望花费尽可能少的钱。形式上，Leha需要选择恰好两份度假券 #cf_span[i] 和 #cf_span[j] #cf_span[(i ≠ j)]，使得它们不重叠，持续时间之和恰好为 #cf_span[x]，且总花费最小。两份度假券 #cf_span[i] 和 #cf_span[j] 不重叠，当且仅当满足以下至少一个条件：#cf_span[ri < lj] 或 #cf_span[rj < li]。\n\n帮助Leha选择合适的度假券吧！\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[x] #cf_span[(2 ≤ n, x ≤ 2·105)] —— 旅行社中度假券的数量和Leha假期的总时长。\n\n接下来的 #cf_span[n] 行，每行包含三个整数 #cf_span[li]、#cf_span[ri] 和 #cf_span[costi] #cf_span[(1 ≤ li ≤ ri ≤ 2·105, 1 ≤ costi ≤ 109)] —— 描述一份度假券。"}},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[x] #cf_span[(2 ≤ n, x ≤ 2·105)] —— 旅行社中度假券的数量和Leha假期的总时长。接下来的 #cf_span[n] 行，每行包含三个整数 #cf_span[li]、#cf_span[ri] 和 #cf_span[costi] #cf_span[(1 ≤ li ≤ ri ≤ 2·105, 1 ≤ costi ≤ 109)] —— 描述一份度假券。"},{"iden":"output","content":"请输出一个整数，表示Leha将花费的最少金额；如果无法选择两份不重叠且持续时间之和恰好为 #cf_span[x] 的度假券，则输出 #cf_span[ - 1]。"},{"iden":"examples","content":"输入\n4 5\n1 3 4\n1 2 5\n5 6 1\n1 2 4\n输出\n5\n\n输入\n3 2\n4 6 3\n2 4 1\n3 5 4\n输出\n-1"},{"iden":"note","content":"在第一个样例中，Leha应选择第一份和第三份度假券。此时总持续时间为 #cf_span[(3 - 1 + 1) + (6 - 5 + 1) = 5]，总花费为 #cf_span[4 + 1 = 5]。\n\n在第二个样例中，每份度假券的持续时间均为 #cf_span[3]，因此不可能选出两份持续时间之和恰好为 #cf_span[2] 的度假券。"}]

**Definitions** Let $ n, x \in \mathbb{Z}^+ $ denote the number of vouchers and the required total vacation duration, respectively. Let $ V = \{ (l_i, r_i, c_i) \mid i \in \{1, \dots, n\} \} $ be the set of vouchers, where: - $ l_i, r_i \in \mathbb{Z}^+ $ are the departure and return days ($ l_i \leq r_i $), - $ c_i \in \mathbb{Z}^+ $ is the cost of voucher $ i $, - The duration of voucher $ i $ is $ d_i = r_i - l_i + 1 $. **Constraints** 1. $ 2 \leq n, x \leq 2 \cdot 10^5 $ 2. $ 1 \leq l_i \leq r_i \leq 2 \cdot 10^5 $, $ 1 \leq c_i \leq 10^9 $ 3. For any two distinct vouchers $ i, j $, they are **disjoint** iff $ r_i < l_j $ or $ r_j < l_i $. 4. We require exactly two distinct vouchers $ i \ne j $ such that: - $ d_i + d_j = x $, - Vouchers $ i $ and $ j $ are disjoint. **Objective** Minimize $ c_i + c_j $ over all pairs $ (i, j) $, $ i \ne j $, satisfying the above constraints. If no such pair exists, output $ -1 $.

Samples

Input #1

Output #1

Input #2

Output #2

\-1

API Response (JSON)

{
  "problem": {
    "name": "C. Hacker, pack your bags!",
    "description": {
      "content": "It's well known that the best way to distract from something is to do one's favourite thing. Job is such a thing for Leha. So the hacker began to work hard in order to get rid of boredom. It means th",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF822C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "It's well known that the best way to distract from something is to do one's favourite thing. Job is such a thing for Leha.\n\nSo the hacker began to work hard in order to get rid of boredom. It means th...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"众所周知，分散注意力的最佳方式就是做自己最喜欢的事情。对Leha来说，编程就是这样的事情。\\n\\n于是，这位黑客开始努力工作以摆脱无聊。这意味着Leha开始在全球范围内黑入计算机。为了表彰这种热情，老板给了黑客整整 #cf_span[x] 天的假期。众所周知，大多数人喜欢外出度假，因此Leha立即去了旅行社。在那里，他发现还剩下 #c...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, x \\in \\mathbb{Z}^+ $ denote the number of vouchers and the required total vacation duration, respectively.  \nLet $ V = \\{ (l_i, r_i, c_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments