题目内容

在一套设备监控系统中，共有 $n$ 个设备。每个设备有一个整数特征值 $h_i$，并可在两种输出数值之间切换：低输出值 $L_i$ 和高输出值 $H_i$。

现在需要选定一个整数阈值 $X$。对于第 $i$ 个设备：

• 若 $h_i < X$，其输出为 $L_i$；
• 若 $h_i \ge X$，其输出为 $H_i$。

记所有设备的输出总和为 $W(X)=\sum_{i=1}^{n} w_i(X)$，其中 $w_i(X)$ 是第 $i$ 个设备在阈值 $X$ 下的输出。

给定一个目标总和 $S$，请在所有整数 $X$ 中，找出 $|W(X)-S|$ 的最小值，并输出这个最小值。

数据范围：

• 设备数量 $n$ 满足 $1 \le n \le 250000$；
• 目标总和 $S$ 的绝对值不超过 $9 \times 10^{17}$；
• 每个 $h_i,L_i,H_i$ 的绝对值不超过 $8 \times 10^8$。

输入描述

第一行包含一个整数 $n$，表示设备数量。 第二行包含一个整数 $S$，表示目标总和。 接下来 $n$ 行，第 $i$ 行包含三个整数 $h_i$、$L_i$、$H_i$，分别表示第 $i$ 个设备的特征值、低输出值和高输出值。

输出描述

输出一个非负整数，表示所有整数阈值 $X$ 中 $|W(X)-S|$ 能够取得的最小值。

样例1

输入

2
10
1 2 5
3 4 8

输出

0

说明

初始时阈值足够小，所有设备都取高输出，总和为 $H_1+H_2=5+8=13$，与目标 $S=10$ 的差为 $|13-10|=3$。

当阈值取 2 时，设备 1 的 $h_1=1<2$，因此输出低值 $L_1=2$；设备 2 的 $h_2=3\ge2$，仍输出高值 $H_2=8$。此时 $W(2)=2+8=10$，与 $S$ 的差为 0，达到最小值。

样例2

输入

2
5
2 1 4
2 3 7

输出

1

说明

初始时阈值足够小，所有设备输出高值，总和为 $4+7=11$，与目标 $S=5$ 的差为 6。

两个设备的特征值都是 $h_i=2$。当阈值 $X>2$ 时，它们会一起切换为低值，总和变为 $1+3=4$，与 $S$ 的差为 1。由于相同的 $h_i$ 必须同时切换，不存在只切换一个设备的阈值状态，因此最小值为 1。

样例3

输入

1
0
0 -5 5

输出

5

说明

只有一个设备。初始时设备输出高值 $H_1=5$，与目标 $S=0$ 的差为 5。

当阈值 $X>0$ 时，设备切换为低值 $L_1=-5$，此时 $|-5-0|=5$。因此所有可能的阈值下差距都是 5，最小值为 5。