一群臭烘烘、丑陋的绿皮怪正准备毒害马里博尔的象征——那株 450 年树龄的葡萄藤！它们聚集在 Kodžak 纪念碑周围，在踏上前往德拉瓦河左岸著名的 Lent 街（那株古老葡萄藤生长的地方）的征程前，正在敲定它们的计划！你，这位强大的紫罗兰战士，已被召唤去在敌人实施其致命行径之前消灭它们！

总共有 $n$ 个敌人，每个敌人都有三个属性：恶臭度、绿色度和丑陋度。对于每个 $i \in \{1, \dots, n\}$，整数 $a_i, b_i, c_i$ 分别决定了第 $i$ 个敌人的恶臭度、绿色度和丑陋度。另一方面，你有两个属性：力量和紫罗兰度。整数 $X$ 和 $Y$ 分别决定了你的力量和紫罗兰度水平。

作为一名自豪的马里博尔人（Mariborčan / Mariborčanka），你的紫罗兰度（$Y$）水平在你出生时就已确定，且永远不会改变。然而，通过击败敌人，你的力量（$X$）会增加。具体来说，当你击败敌人 $i$ 时，$X$ 会增加该敌人的丑陋度，即增加 $c_i$。你可以按任意顺序一个接一个地击败敌人，但你只有在你的力量大于其恶臭度（$X \ge a_i$）且你的紫罗兰度大于其绿色度（$Y \ge b_i$）时，才能击败敌人 $i$。此外，每个敌人只能被击败一次。

你一定想知道击败至少 $k$ 个敌人所需的初始力量与紫罗兰度之和（即 $X + Y$）的最小值。编写一个程序来求出这个值！

输入格式

第一行包含整数 $n$ 和 $k$。接下来的 $n$ 行中，第 $i$ 行（对于 $i \in \{1, \dots, n\}$）包含整数 $a_i, b_i, c_i$。

输出格式

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

数据范围

• $1 \le n \le 2 \cdot 10^5$
• $1 \le k \le n$
• $0 \le a_i, b_i, c_i \le 10^9$

子任务

1. (19 分) $n \le 1000$
2. (15 分) 对于所有 $i \in \{1, \dots, n\}$，$b_i = 0$
3. (24 分) 对于所有 $i \in \{1, \dots, n\}$，$c_i = 0$
4. (42 分) 无附加限制

样例

输入 1

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

输出 1

12

说明 1

为了击败至少四个敌人，初始时 $X = 5$ 和 $Y = 7$ 就足够了。首先，你击败敌人 2，使你的 $X$ 增加到 8。现在，你可以消灭敌人 1 并使 $X$ 达到 12。有了这个力量水平，你可以击败敌人 5，使 $X$ 达到 21。你通过消灭敌人 4 完成了你的任务。