1356: [STT2024MarR1] 邪恶蝴蝶

第二天起来，花园又被破坏了。

由于每次花园都被邪恶蝴蝶破坏，所以三花猫 XXY、猪猪五花肉、地地完全急了，打算找些办法对付邪恶蝴蝶。他们在桃花源的公共图书馆发现了一本奇特的书，书上记载：

邪恶蝴蝶（Evil Butterfly）早在古代就已存在，以四处采花顺便毁坏庄稼闻名。她在各地都有独特的称呼，例如在 FJ 叫歹势福蝶；在 GD 叫霞啊唔哋；在 HL、JL、LN 叫损色扑楞蛾子；在 SX 叫狡猾花哒；在 SC 叫仙人板板哦哦儿；在 RB 叫恶翅凤。邪恶蝴蝶常和她的表亲摩斯拉（Mothzilla）一起出没。摩斯拉是邪恶的飞蛾，所过之处都会被带辐射的蛾尘侵蚀，导致当地辐射超标。

在花园门口插上邪恶蝴蝶驱赶器是一种有效对付邪恶蝴蝶的方法。邪恶蝴蝶驱赶器制作步骤和使用方法如下：

1. 在恒河水萃取物中加入游离电子，然后和压缩黑洞混合。
2. 将混合物放在便携式托卡马克中，然后将托卡马克固定在铁杆上。这样邪恶蝴蝶驱赶器就完成了。
3. 将邪恶蝴蝶驱赶器插到花园门口，这样邪恶蝴蝶就不敢到驱赶器的方圆 $1 \text{km}^2$ 内。

通过一些技术手段，三花猫 XXY、猪猪五花肉、地地成功制作了邪恶蝴蝶驱赶器。村里人为了感谢他们，送来冬天也不会枯萎，还散发着浓郁芳香的花。然而三花猫 XXY、猪猪五花肉、地地的花园是有限的。



花园的面积是 $M$，现在花园里被破坏得什么也没有。村民送来了 $N$ 簇花，第 $i$ 簇花的占地面积为 $w_i$，美观度为 $p_i$，香气散发程度为 $s_i$。每簇花只能种植一次，不种的花会还给村民。

花园的气运被定义如下：

$$
\lvert \sum_{i \in C}p_i - \sum_{i \in C}s_i \rvert
$$

其中，$C$ 为选择种植的花束集合。定义 $\lvert C \rvert=\sum_{i \in C}w_i$。为了花园容得下，三只还需保证$\lvert C \rvert \leq M$。

三只希望求出一种方案使花园内花在不超过占地面积的情况下，气运尽量大，这样就能带来好运。

第一行两个整数 $N,M$，表示有几簇花和花园面积。

接下来 $N$ 行，每行有两个整数 $w_i$，$p_i$，$s_i$，表示这种花的占地面积、美观度、香气散发程度。

一个数，表示花园的最大气运。

3 4
3 0 2
3 2 0
1 0 3

5