Radio Watchtowers

The border between Bulgaria and Romania is the Danube. Many people cross the river by boat, so the rescue service built $N$ watchtowers on the Bulgarian bank. Treat the river as a straight line and the towers as points with integer coordinates on it. Tower $i$ stands $X_i$ meters downstream from the place where the river enters Bulgaria.

Each tower carries one radio, and the radio in tower $i$ has power $P_i$. Two towers $i$ and $j$ communicate directly when the distance between them is at most the sum of the two powers, that is when $|X_i - X_j| \le P_i + P_j$.

To cut costs, only $K$ towers will be kept and the other $N - K$ will be sold. Selling tower $i$ brings in $S_i$, but that tower can no longer be used. Every two of the $K$ kept towers must communicate directly. When only one tower is kept, the communication requirement is dropped. The current powers may not be enough, so the power of a kept tower can be raised. Raising a power by $1$ costs $1$.

Choose the $N - K$ towers to sell and raise the powers of the kept towers so that the requirement holds. Find the smallest possible value of the money spent on raising powers minus the money earned from the sales.

The first line has two integers $N$ and $K$: the number of towers at the start and the number of towers to keep.

Each of the next $N$ lines has three integers $X_i$, $P_i$, $S_i$: the position of tower $i$, its initial power, and its sale price. The towers are given in increasing order of $X_i$, and no two towers share a position.

Print one integer on a single line: the smallest possible value of the money spent on raising powers minus the money earned from the sales. Print a negative number when the sales bring in more than the raises cost.

• $1 \le K \le N \le 100\,000$
• $1 \le X_i, P_i, S_i \le 10^9$

In the first example, keeping towers 1, 3 and 4 is one optimal choice. Raising the power of tower 1 by $17$ and the power of tower 4 by $31$ costs $48$, and selling towers 2 and 5 earns $4 + 2 = 6$. The answer is $48 - 6 = 42$.

In the second example, towers 2, 3, 6, 7 and 9 can be kept. Raising the power of tower 7 by $2$ and the power of tower 9 by $4$ costs $6$, and selling towers 1, 4, 5 and 8 earns $4 + 6 + 9 + 11 = 30$. The answer is $6 - 30 = -24$, a gain of $24$.