/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 233 点
問題文
高橋君はオンラインショッピングサイトで開催されるタイムセールに参加しようとしています。
このセールでは N 個の商品が出品される予定です。i 番目の商品（1 \leq i \leq N）は時刻 T_i に出品開始され、価格は H_i 円で、満足度は B_i です。
高橋君がサイトを閲覧できる時間帯は時刻 S から時刻 E までの間（両端を含む）に限られています。高橋君は、出品開始時刻がこの時間帯に含まれる商品のみ購入できます。
さらに、高橋君は価格が K 円以上の商品のみに興味があるため、価格が K 円未満の商品は購入しません。
高橋君の所持金は十分にあり、購入個数にも制限はありません。高橋君は以下の条件を 両方とも 満たす商品をすべて購入します。
- 出品開始時刻 T_i が S 以上 E 以下である（S \leq T_i \leq E）
- 価格 H_i が K 以上である（H_i \geq K）
高橋君が購入するすべての商品の満足度の合計を求めてください。条件を満たす商品が存在しない場合、満足度の合計は 0 とします。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 1 \leq S \leq E \leq 10^9
- 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数
- 満足度の合計（出力する値）は 2 \times 10^{14} 以下であることが保証される
入力
N K S E T_1 H_1 B_1 T_2 H_2 B_2 \vdots T_N H_N B_N
- 1 行目には、商品の総数を表す N 、購入対象とする最低価格を表す K 、閲覧開始時刻を表す S 、閲覧終了時刻を表す E が、スペース区切りで与えられる。
- 2 行目から N + 1 行目では、各商品の情報が与えられる。
- 1 + i 行目では、 i 番目の商品の出品開始時刻 T_i 、価格 H_i 、満足度 B_i が、スペース区切りで与えられる。
出力
条件を満たす商品の満足度の合計を 1 行で出力してください。
入力例 1
5 100 10 20 15 150 30 8 200 50 12 80 40 18 100 25 25 300 60
出力例 1
55
入力例 2
7 500 100 500 150 600 100 50 1000 200 200 400 80 300 500 150 450 800 120 600 700 90 100 500 50
出力例 2
420
入力例 3
10 1000000 500000000 800000000 100000000 2000000 500 500000000 1000000 300 600000000 1500000 400 750000000 500000 200 800000000 2000000 600 900000000 3000000 700 550000000 1000000 350 700000000 800000 150 650000000 1200000 450 400000000 1500000 250
出力例 3
2100
Score : 233 pts
Problem Statement
Takahashi is planning to participate in a time sale held on an online shopping site.
In this sale, N items are scheduled to be listed. The i-th item (1 \leq i \leq N) becomes available at time T_i, has a price of H_i yen, and a satisfaction value of B_i.
Takahashi can browse the site only during the time period from time S to time E (inclusive). Takahashi can only purchase items whose listing start time falls within this time period.
Furthermore, Takahashi is only interested in items priced at K yen or more, so he will not purchase items priced less than K yen.
Takahashi has sufficient funds and there is no limit on the number of items he can purchase. Takahashi will purchase all items that satisfy both of the following conditions:
- The listing start time T_i is between S and E inclusive (S \leq T_i \leq E)
- The price H_i is at least K (H_i \geq K)
Find the total satisfaction value of all items Takahashi purchases. If no items satisfy the conditions, the total satisfaction value is 0.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 1 \leq S \leq E \leq 10^9
- 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
- All input values are integers
- It is guaranteed that the total satisfaction value (the output value) is at most 2 \times 10^{14}
Input
N K S E T_1 H_1 B_1 T_2 H_2 B_2 \vdots T_N H_N B_N
- The first line contains N representing the total number of items, K representing the minimum price for purchase consideration, S representing the browsing start time, and E representing the browsing end time, separated by spaces.
- From the 2nd line to the (N + 1)-th line, information about each item is given.
- The (1 + i)-th line contains the listing start time T_i, the price H_i, and the satisfaction value B_i of the i-th item, separated by spaces.
Output
Output the total satisfaction value of the items satisfying the conditions in a single line.
Sample Input 1
5 100 10 20 15 150 30 8 200 50 12 80 40 18 100 25 25 300 60
Sample Output 1
55
Sample Input 2
7 500 100 500 150 600 100 50 1000 200 200 400 80 300 500 150 450 800 120 600 700 90 100 500 50
Sample Output 2
420
Sample Input 3
10 1000000 500000000 800000000 100000000 2000000 500 500000000 1000000 300 600000000 1500000 400 750000000 500000 200 800000000 2000000 600 900000000 3000000 700 550000000 1000000 350 700000000 800000 150 650000000 1200000 450 400000000 1500000 250
Sample Output 3
2100