「BalkanOI 2023 Day2」Save the Vine!

题目描述

译自 BalkanOI 2023 Day2 T2「Save the Vine!」

一群又臭又丑的绿色小人准备毒死 450 年历史的葡萄藤，这是马里博尔的象征！你，强大的紫色战士，被召唤来在他们实施致命的行动之前消灭敌人！

一共有 $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$ 的最小初始值。

样例

输入

5 4
8 3 4
5 2 3
10 9 10
20 4 6
12 7 9

输出

12

说明
为了击败至少四个敌人，只需要从 $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}$

详细子任务附加限制及分值如下表所示。