問題一覧 > 通常問題

No.2808 Concentration

レベル : / AI推定難易度 : 1750 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 36
作問者 : watasou1543 / テスター : hirayuu_yc Magentor penguin8331 highlighter warabi0906 keisuke6 silv723 zeta7532 fact493 Yoyoyo8128
お気に入りにしたユーザー ProblemId : 11082 / 自分の提出
問題文最終更新日: 2024-07-12 20:54:42
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 436 ('09 Contest 002 day1) (順位表) の他の問題:

Problem Statement

watasou is attending a class.

Since watasou can foresee the future, he knows that Professor warabi will give $N$ important talks. Taking the start of the class as $0$ minutes, the $i$-th important talk runs from $X_i+10^{100}+0.01$ minutes to $Y_i+10^{100}-0.01$ minutes, and by listening to it from beginning to end he gains $Z_i$ knowledge.

watasou can listen to the class if and only if he is awake. Since watasou cannot keep his concentration during Professor warabi's class, he can stay awake for at most $S$ consecutive minutes. Also, once he falls asleep, he cannot wake up for at least $H$ minutes.

When watasou can freely decide the times at which he sleeps and wakes under the above conditions, find the maximum possible total knowledge he can gain.

Input

The input is given from Standard Input in the following format. 
$N ~~~ S ~~~ H$
$X_{1} ~~~ Y_{1}~~~ Z_{1}$
$X_{2} ~~~ Y_{2} ~~~ Z_{2}$
$~~~~~~~~ \vdots$
$X_{N} ~~ Y_{N} ~~ Z_{N}$

Constraints

  • $1 \leq N \leq 2×10^5$
  • $1 \leq S,H \leq 10^9$
  • $0 \leq X_{i} \lt Y_{i} \leq 10^{9} \left( 1 \leq i \leq N\right)$
  • $Y_{i} \lt X_{j} \left(1 \leq i \lt j \leq N \right)$
  • $1 \leq Z_i \leq 10^9$
  • All input values are integers.

Output

Output the answer.

Sample

Sample 1
Input
4 2 2
1 3 4
5 8 6
9 11 5
12 13 2
Output
9

He can gain $9$ knowledge by acting as follows.

  • Sleep for $10^{100}+1.01$ minutes.
  • Listen to the $1$st talk, increasing his knowledge by $4$.
  • Sleep for $6.02$ minutes.
  • Listen to the $3$rd talk, increasing his knowledge by $5$.
No matter how he decides the times to sleep and wake, he cannot gain $10$ or more knowledge, so this is optimal.
Note that the $2$nd talk lasts $2.98$ minutes, so he cannot listen to it from beginning to end.

Sample 2
Input
1 1 1
0 100 100
Output
0

Sample 3
Input
3 3 4
0 3 4
5 8 7
11 12 5
Output
9

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。