Save the Vine!

This problem is adapted from BalkanOI 2023 Day2 T2 "Save the Vine!".

You are a mighty purple warrior called upon to stop a horde of nasty, green enemies from poisoning a 450‐year–old vine – a symbol of the city of Maribor. The enemies have gathered around the Kodžak monument and plan to march to the famous Lent street on the left bank of the Drava River, where the ancient vine grows.

There are n enemies. The i^th enemy has three attributes: stink, greenness, and ugliness which are represented by the integers \(a_i\), \(b_i\), and \(c_i\) respectively. You have two attributes: power \(X\) and purpleness \(Y\). Your purpleness \(Y\) is fixed at birth while your power \(X\) increases as you defeat enemies. When you defeat enemy \(i\), your power increases by \(c_i\).

You can defeat the enemies in any order, but you can only defeat enemy \(i\) if your current power satisfies \(X \ge a_i\) and your fixed purpleness satisfies \(Y \ge b_i\). Each enemy can only be defeated once.

Your task is to determine the minimum possible sum \(X+Y\) (i.e. the sum of your initial power and purpleness) so that you are able to defeat at least k enemies. You are allowed to choose the initial values \(X\) and \(Y\) (with \(Y\) remaining constant during the fight) in any way as long as \(X+Y\) is minimized.

Note on Formulas

• \(a_i\): the stink value of the \(i\)th enemy
• \(b_i\): the greenness value of the \(i\)th enemy
• \(c_i\): the ugliness value (reward) of the \(i\)th enemy
• \(X\): your power (which increases when you defeat an enemy)
• \(Y\): your fixed purpleness

inputFormat

The first line contains two integers n and k (1 ≤ k ≤ n), where n is the number of enemies and k is the minimum number of enemies you must defeat.

The next n lines each contain three integers \(a_i\), \(b_i\), and \(c_i\) (each non‐negative), representing the stink, greenness, and ugliness values of the i^th enemy, respectively.

You may assume that all input values are such that a solution exists.

outputFormat

Output a single integer — the minimum possible sum \(X+Y\) needed to defeat at least k enemies.

sample

3 2
2 1 1
5 3 2
4 2 2

5