题目内容

在一套批量参数配置系统中，每个配置项都会根据统一的切换界限，在两种预设数值之间选择其一。现在希望通过调整这个界限，使所有配置项的最终汇总结果尽可能接近期望值。

给定 $n$ 个配置项，第 $i$ 个配置项包含三个整数：触发值 $p_i$、前置值 $A_i$ 和后置值 $B_i$。

你可以任意选择一个整数界限 $X$。确定 $X$ 后，第 $i$ 个配置项的最终数值 $w_i$ 按照下面的规则确定：

1. 当 $p_i<X$ 时，$w_i=A_i$；
2. 当 $p_i\ge X$ 时，$w_i=B_i$。

所有配置项的汇总值定义为

给定目标值 $G$，你需要在所有整数 $X$ 中，找到使

尽可能小的方案，并输出这个最小值。

输入描述

第一行输入一个整数 $n\ (1\le n\le 250000)$，表示配置项的数量。

第二行输入一个整数 $G\ (-9\times10^{17}\le G\le9\times10^{17})$，表示目标汇总值。

接下来 $n$ 行，第 $i$ 行输入三个整数

分别表示第 $i$ 个配置项的触发值、前置值和后置值。

输出描述

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

样例1

输入

4
20
2 3 10
2 1 7
5 4 9
8 -2 6

输出

1

说明

不同的整数界限只会在越过某个触发值时改变配置项的取值。

当 $X\le2$ 时，四个配置项均取后置值，此时

当 $3\le X\le5$ 时，前两个配置项改取前置值，因此

当 $6\le X\le8$ 时，前三个配置项取前置值，此时

当 $X\ge9$ 时，所有配置项均取前置值，此时

它们与目标值 $20$ 的绝对差分别为 $12,1,6,14$，因此答案为 $1$。

样例2

输入

3
-4
-1 -5 2
3 1 -4
6 0 -2

输出

0

说明

选择任意满足 $X\le-1$ 的整数界限时，三个配置项都会取后置值，因此

汇总值恰好等于目标值 $G=-4$，所以最小绝对差为 $0$。

样例3

输入

1
700000000000
4 -800000000 800000000

输出

699200000000

说明

只有一个配置项。

当 $X\le4$ 时，它取后置值 $800000000$，此时绝对差为

当 $X\ge5$ 时，它取前置值 $-800000000$，此时绝对差为

因此最小值为 $699200000000$。