4249. 最大价值

【题目描述】

有$n$个区间和$m$个层级，每个区间唯一隶属于其中一个层级：第$i$个区间属于第$a_i$层，具有价值$w_i$，区间范围为闭区间 [$l_i,r_i$]

现需从这些区间中选择一个子集，满足以下两个条件：

1：每个层级最多选择一个区间（即对任意层级$k$，最多选 1 个隶属于$k$层的区间）；

2：若选中了第$k$层的区间 [$L,R$]，则所有隶属于后续层级（即层号$k′>k$）的选中区间 [$L′,R′$]，必须满足$L′>R$（后续层级的区间左端点严格大于当前层级区间的右端点，等价于：后续区间既不能与当前区间重叠，也不能出现在当前区间的左侧/更靠前的位置）。

请计算满足上述约束的区间子集的最大总价值（若不选择任何区间，总价值为0）。

输入：/upload/file/20260108/20260108193158_48314.txt

输出：/upload/file/20260108/20260108193207_43453.txt

【输入格式】

第一行，输入$n，m$

后面$n$行，输入$a_i,w_i,l_i,r_i$

【输出格式】

输出最大价值

【样例输入】

4 2
1 5 1 3
1 3 2 4
2 4 5 7
2 6 6 8

【样例输出】

11

【样例说明】

最优选择：

第一层：[1,3]

第二层：[6,8]

最优答案为11，可以证明，这是最优解

【数据规模与约定】

对于10%的数据，$m≤10$

对于30%的数据，$n≤200$

对于50%的数据，$n≤1000,m≤20$

对于另外5%的数据，对于所有的i,$l_i=r_j+1,其中j=i-1$

对于另外5%的数据，对于所有的i,$r_i-l_i=k$

对于100%的数据，$1≤m≤n≤10^5,1≤w_i≤10^5,1≤l_i≤r_i≤10^9$