P11166 [BalkanOI 2023] Save the Vine!

**译自 [BalkanOI 2023](https://boi2023.zotks.si) Day2 T2「[Save the Vine!](https://boi2023.zotks.si/wp-content/uploads/day_2/d2_vine/en.pdf)」** 一群又臭又丑的绿色小人准备毒死 450 年历史的葡萄藤，这是马里博尔的象征！他们正在 Kodžak 纪念碑周围聚集，制定他们的计划，准备向 Drava 河左岸的著名 Lent 街上的房子进军，那里就是那棵古老的葡萄藤生长的地方！你，强大的紫色战士，被召唤来在他们实施致命的行动之前消灭敌人！ 一共有 $n$ 个敌人，每个敌人都有三个属性：臭度、绿度和丑度。对于每个 $i \in\{1, \ldots, n\}$，整数 $a_{i}, b_{i}$ 和 $c_{i}$ 分别决定了第 $i$ 个敌人的臭度、绿度和丑度。而你有两个属性：力量 $X$ 和紫度 $Y$。 作为一个自豪的马里博尔人，你的紫度 $Y$ 在你出生时就已经确定，永远不会改变。但是，通过击败敌人，你的力量 $X$ 会增加。特别地，当你击败敌人 $i$ 时，$X$ 会增加该敌人的丑度 $c_{i}$。你可以按任意顺序一个一个地击败敌人，但你只能在你的力量大于他的臭度（$X \geq a_{i}$）且你的紫度大于他的绿度（$Y \geq b_{i}$）时击败敌人 $i$。另外，你只能击败每个敌人一次。 你肯定想知道，为了击败至少 $k$ 个敌人，你最初的力量和紫度（即 $X+Y$）的最小和是多少。编写一个程序来找到这个值！

第一行包含整数 $n$ 和 $k$。接下来的 $n$ 行中的第 $i\ (1\leq i\leq n)$ 行包含整数 $a_{i}, b_{i}$ 和 $c_{i}$。

输出至少击败 $k$ 个敌人所需的 $X+Y$ 的最小初始值。

### 样例解释 为了击败至少四个敌人，只需要从 $X=5$ 和 $Y=7$ 开始。首先，你击败敌人 $2$，将你的 $X$ 提升到 $8$。现在，你可以摧毁敌人 $1$，并达到 $X=12$。有了这样的力量，你可以击败敌人 $5$，达到 $X=21$。你完成你的任务，消灭敌人 $4$。 ### 数据范围 对于所有输入数据，满足： - $1 \leq n \leq 2 \cdot 10^{5}$ - $1 \leq k \leq n$ - $0 \leq a_{i}, b_{i}, c_{i} \leq 10^{9}$ 详细子任务附加限制及分值如下表所示。 | 子任务编号 | 附加限制 | 分值 | | :--: | :--: | :--: | | $1$ | $n \leq 1000$ | $19$ | | $2$ | $b_{i}=0\ (1\leq i\leq n)$ | $15$ | | $3$ | $c_{i}=0\ (1\leq i\leq n)$ | $24$ | | $4$ | 无附加限制 | $42$ |