#include <stdio.h>
#define N 100000
#define INF 0x3f3f3f3f3f3f3f3fLL
long long min(long long a, long long b) { return a < b ? a : b; }
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int xx[N * 2], n, k;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (xx[ii[j]] == xx[i_])
j++;
else if (xx[ii[j]] < xx[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
int cc[6][N], iq[6][N + 1], pq[N], tt[N], cnt[6], t;
int lt(int i, int j) { return cc[t][i] < cc[t][j]; }
int p2(int p) {
return (p *= 2) > cnt[t] ? 0 : (p < cnt[t] && lt(iq[t][p + 1], iq[t][p]) ? p + 1 : p);
}
void pq_up(int i) {
int p, q, j;
for (p = pq[i]; (q = p / 2) && lt(i, j = iq[t][q]); p = q)
iq[t][pq[j] = p] = j;
iq[t][pq[i] = p] = i;
}
void pq_dn(int i) {
int p, q, j;
for (p = pq[i]; (q = p2(p)) && lt(j = iq[t][q], i); p = q)
iq[t][pq[j] = p] = j;
iq[t][pq[i] = p] = i;
}
void pq_add(int i) {
pq[i] = ++cnt[t], tt[i] = t, pq_up(i);
}
int pq_remove(int i) {
int j = iq[t][cnt[t]--];
if (j != i)
pq[j] = pq[i], pq_up(j), pq_dn(j);
pq[i] = 0, tt[i] = -1;
return i;
}
long long sum; int x;
long long cost(int t, int i) {
return (long long) cc[t][i] * ((t & 1) == 0 ? -1 : 1) + (1 - (t / 2)) * x;
}
void balance() {
int t1, t2, i1, i1_, i2, i2_;
long long c1, c1_, c2, c2_;
check:
for (t1 = 0; t1 < 6; t1 += 2)
for (t2 = 1; t2 < 6; t2 += 2)
if (cnt[t1] && cnt[t2]) {
i1 = iq[t1][1], i2 = iq[t2][1];
if (cost(t1, i1) > cost(t2, i2)) {
t = t1, pq_remove(i1), sum -= -cc[t1][i1];
t = t1 ^ 1, pq_add(i1);
t = t2, pq_remove(i2);
t = t2 ^ 1, pq_add(i2), sum += -cc[t2 ^ 1][i2];
goto check;
}
}
while (cnt[0] + cnt[2] + cnt[4] < k) {
c2_ = INF, i2_ = -1;
for (t2 = 1; t2 < 6; t2 += 2)
if (cnt[t2]) {
i2 = iq[t2][1], c2 = cost(t2, i2);
if (c2_ > c2)
c2_ = c2, i2_ = i2;
}
i2 = i2_, t2 = tt[i2];
t = t2, pq_remove(i2);
t = t2 ^ 1, pq_add(i2), sum += -cc[t2 ^ 1][i2];
}
while (cnt[0] + cnt[2] + cnt[4] > k) {
c1_ = -INF, i1_ = -1;
for (t1 = 0; t1 < 6; t1 += 2)
if (cnt[t1]) {
i1 = iq[t1][1], c1 = cost(t1, i1);
if (c1_ < c1)
c1_ = c1, i1_ = i1;
}
i1 = i1_, t1 = tt[i1];
t = t1, pq_remove(i1), sum -= -cc[t1][i1];
t = t1 ^ 1, pq_add(i1);
}
}
long long eval() {
return sum + (long long) (cnt[0] - cnt[4]) * x;
}
int main() {
static int ww[N], ii[N * 2];
int h, i, i_;
long long w, ans;
scanf("%d%d", &n, &k);
w = 0;
for (i = 0; i < n; i++) {
int p;
scanf("%d%d%d", &x, &p, &ww[i]);
w += ww[i];
xx[i << 1 | 0] = x - p, xx[i << 1 | 1] = x + p;
cc[0][i] = -(ww[i] - xx[i << 1 | 1]), cc[1][i] = ww[i] - xx[i << 1 | 1];
cc[2][i] = -ww[i], cc[3][i] = ww[i];
cc[4][i] = -(ww[i] + xx[i << 1 | 0]), cc[5][i] = ww[i] + xx[i << 1 | 0];
}
for (i = 0; i < n * 2; i++)
ii[i] = i;
sort(ii, 0, n * 2);
for (i = 0; i < n; i++)
t = 5, pq_add(i);
ans = INF;
for (h = 0; h < n * 2; h++) {
i_ = ii[h], i = i_ >> 1, x = xx[i_];
if ((i_ & 1) == 0) {
t = tt[i], pq_remove(i);
if ((t & 1) == 0)
sum -= -cc[t][i];
t = 3, pq_add(i);
} else {
t = tt[i], pq_remove(i);
if ((t & 1) == 0)
sum -= -cc[t][i];
t = 1, pq_add(i);
}
balance();
ans = min(ans, eval() - w);
}
printf("%lld\n", ans);
return 0;
}
