Description

An army of stinky ugly green men is set to poison the 450-year-old vine, the symbol of Maribor! They are gathering around the Kodžak monument, finalizing their plans before embarking on their march to the house on the famous Lent street on the left bank of Drava, where the venerable vine grows! You, the strong violet warrior, have been summoned to destroy the enemies before they manage to do their deadly deed!

There are a total of $n$ enemies, and each of them has three properties: stinkiness, greenness, and ugliness. For each $i \in\{1, \ldots, n\}$, integers $a_{i}, b_{i}$, and $c_{i}$ determine the level of stinkiness, greenness, and ugliness of the $i$-th enemy, respectively. You, on the other hand, have two properties: strength and violetness. The integers $X$ and $Y$ determine the level of your strength and violetness, respectively.

Being a proud Mariborčan / Mariborčanka, the level of your violetness ($Y$) was determined at your birth and can never change. However, by defeating enemies, your strength ($X$) increases. In particular, when you defeat enemy $i, X$ is increased by the level of that enemy's ugliness, i.e., by $c_{i}$. You can defeat enemies one by one in any order, but you can defeat enemy $i$ only if your strength is greater than his stinkiness ($X \geq a_{i}$) and your violetness is greater than his greenness ($Y \geq b_{i}$). Additionally, you can defeat each enemy only once.

You would surely want to know the minimum sum of your initial strength and violetness (i.e., $X+Y$) that is necessary to defeat at least $k$ enemies. Write a program to find this value!

Input format

The first line contains the integers $n$ and $k$. The $i$-th of the following $n$ lines (for $i \in\{1, \ldots, n\}$) contains the integers $a_{i}, b_{i}$, and $c_{i}$.

Output format

Output the minimum initial value of $X+Y$ required to defeat at least $k$ enemies.

Input bounds

• $1 \leq n \leq 2 \cdot 10^{5}$.
• $1 \leq k \leq n$.
• $0 \leq a_{i}, b_{i}, c_{i} \leq 10^{9}$.

Subtasks

1. (19 points) $n \leq 1000$.
2. (15 points) For all $i \in\{1, \ldots, n\}, b_{i}=0$.
3. (24 points) For all $i \in\{1, \ldots, n\}, c_{i}=0$.
4. (42 points) No additional constraints.

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

12

To defeat at least four enemies, it suffices to start with $X=5$ and $Y=7$. First, you defeat enemy $2$, raising your $X$ to $8$. Now, you can destroy enemy $1$ and achieve $X=12$. With this level of strength, you can beat enemy $5$, attaining $X=21$. You complete your mission by eliminating enemy $4$.