#P4276. [ONTAK2015]Bajtman i Okrągły Robin

    ID: 3494 传统题 1000ms 512MiB 尝试: 769 已通过: 214 难度: 7 上传者: 标签>CF2300提高+/省选-二分图建模拟阵贪心增广路广度优先搜索普通并查集路径压缩路径恢复优化建图

[ONTAK2015]Bajtman i Okrągły Robin

[ONTAK2015] Bajtman i Okrągły Robin

题目背景

警告:滥用本题评测将被封号!

题目描述

有 nn 个强盗,其中第 ii 个强盗会在 $[a_i, a_i + 1], [a_i + 1, a_i + 2], \cdots, [b_i - 1, b_i]$ 这么多段长度为 11 的时间中选出一个时间进行抢劫,并计划抢走 cic_i 元。作为保安,你在每一段长度为 11 的时间内最多只能制止一个强盗,那么你最多可以挽回多少损失呢?

输入格式

第一行,一个整数 nn;

接下来 nn 行,每行三个整数 ai,bi,cia_i, b_i, c_i。

输出格式

一行,一个整数,表示所求的值。

样例 #1

样例输入 #1

4
1 4 40
2 4 10
2 3 30
1 3 20

样例输出 #1

90

提示

对于 100%100\% 的数据,1≤n≤5×1031 \leq n \leq 5 \times 10^3,1≤ai<bi≤5×1031 \leq a_i < b_i \leq 5 \times 10^3,1≤ci≤1041 \leq c_i \leq 10^4。