무전 감시탑

불가리아와 루마니아의 국경은 도나우강이다. 배로 강을 건너는 사람이 많아서 구조대는 불가리아 쪽 강변에 감시탑 $N$개를 세웠다. 강은 직선이고 감시탑은 그 위의 정수 좌표 점이라고 하자. $i$번 감시탑은 강이 불가리아로 들어오는 지점에서 하류로 $X_i$미터 떨어져 있다.

감시탑마다 무전기가 하나씩 있고, $i$번 감시탑에 있는 무전기의 세기는 $P_i$다. 두 감시탑 $i$와 $j$는 사이의 거리가 두 세기의 합 이하일 때, 즉 $|X_i - X_j| \le P_i + P_j$일 때 서로 직접 통신한다.

비용을 줄이려고 감시탑을 $K$개만 남기고 나머지 $N - K$개는 팔기로 했다. $i$번 감시탑을 팔면 $S_i$를 얻지만 그 감시탑은 더 이상 쓸 수 없다. 남긴 $K$개는 어느 두 개를 골라도 서로 직접 통신해야 한다. 감시탑을 하나만 남기면 통신 조건은 따지지 않는다. 지금 세기로는 이 조건을 만족하지 못할 수 있으므로, 남긴 감시탑의 세기는 올릴 수 있다. 세기를 $1$ 올릴 때마다 비용 $1$이 든다.

팔 감시탑 $N - K$개를 고르고 남긴 감시탑의 세기를 올려서 조건을 만족시킬 때, 세기를 올리는 데 쓴 비용에서 판매 수입을 뺀 값의 최솟값을 구하라.

첫째 줄에 정수 $N$과 $K$가 주어진다. 처음 감시탑의 개수가 $N$, 남길 감시탑의 개수가 $K$다.

다음 $N$개 줄에는 정수 $X_i$, $P_i$, $S_i$가 주어진다. 각각 $i$번 감시탑의 위치, 처음 세기, 판매 가격이다. 감시탑은 위치 $X_i$의 오름차순으로 주어지고, 위치가 같은 감시탑은 없다.

첫째 줄에 세기를 올리는 데 쓴 비용에서 판매 수입을 뺀 값의 최솟값을 정수 하나로 출력한다. 판매 수입이 더 크면 음수를 출력한다.

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

첫 번째 예제에서는 1번, 3번, 4번 감시탑을 남기는 것이 최적해 중 하나다. 1번의 세기를 $17$, 4번의 세기를 $31$ 올려 $48$을 쓰고, 2번과 5번을 팔아 $4 + 2 = 6$을 얻는다. 답은 $48 - 6 = 42$다.

두 번째 예제에서는 2번, 3번, 6번, 7번, 9번 감시탑을 남길 수 있다. 7번의 세기를 $2$, 9번의 세기를 $4$ 올려 $6$을 쓰고, 1번, 4번, 5번, 8번을 팔아 $4 + 6 + 9 + 11 = 30$을 얻는다. 답은 $6 - 30 = -24$이고, $24$만큼 이득이다.