演播（cast）

题目描述

Y 同学负责安排一场持续多日的校园演播活动。活动中心收到 $n$ 个候选节目，第 $i$ 个节目只能在半开时间区间 $[l_i,r_i)$ 内录制，占用演播室的全部设备，并能带来价值 $v_i$。每个节目还属于类型 $t_i$，其中 $t_i$ 只可能为 $0$ 或 $1$。

同一时刻至多录制一个节目。若连续录制的两个节目类型不同，只要前一个节目结束时刻不晚于后一个节目开始时刻，就可以直接衔接。若它们类型相同，设备还需要额外进行 $c$ 个单位时间的复位，因此前一个节目在时刻 $r$ 结束后，后一个节目必须在不早于 $r+c$ 的时刻开始。没有录制节目的时间不产生价值，也不要求必须安排任何节目。

Y 同学希望从候选节目中选择若干个节目，并按照时间顺序完成录制。请计算能够获得的最大总价值。

输入格式

第一行包含两个整数 $n,c$，分别表示候选节目数量和同类型设备复位时间。

接下来 $n$ 行，每行包含四个整数 $l_i,r_i,t_i,v_i$，描述一个候选节目。

输出格式

输出一个整数，表示能够获得的最大总价值。

样例

6 3
1 4 0 8
4 7 1 7
7 10 1 20
7 9 0 9
10 13 0 6
12 15 1 11

35

数据范围与约定

对于所有数据，$1\le n\le 2\times10^5$，$0\le c\le 10^6$，$0\le l_i<r_i\le 10^9$，$t_i\in\{0,1\}$，$1\le v_i\le 10^9$。

性质 A：保证所有节目的类型均为 $0$。

性质 B：保证 $c=0$。