#P18758. [2027年国家集训队互测] Classic Problem

[2027年国家集训队互测] Classic Problem

Classic Problem

题目描述

有 nn 个任务,任务 ii 需要占用 [li,ri][l_i,r_i] 中的一个格子,如果占用的格子编号 ≤ti\le t_i,则额外获得 11 奖励,求所有任务都完成的情况下能获得的最大奖励。

输入格式

一行两个整数 n,mn,m,分别是任务的数量和格子数量。

接下来 nn 行,一行三个整数 l,r,tl,r,t 表示一个任务。

输出格式

如果无法完成所有任务,输出 −1-1,否则输出答案。

样例 #1

样例输入

3 3
1 2 1
1 2 1
2 3 2

样例输出

1

样例解释

将任务依次分配给 1,2,31,2,3 格子,可知有一个任务能获得奖励。

数据范围

对于所有数据,满足 $1\le n,m\le 5\times 10^5, 1\le l_i \le t_i \le r_i \le m$。

子任务 分值 特殊限制
11 33 n,m≤15n,m \le 15
22 1212 所有 lil_i 相等
33 所有 tit_i 相等
44 1919 n,m≤500n,m \le 500
55 2020 n,m≤2000n,m \le 2000
66 2121 n,m≤105n,m \le 10^5
77 2222 n,m≤5×105n,m \le 5\times 10^5

开启了合理的子任务依赖。

样例附件