#include <stdio.h>
#define N 100000
#define X 1000000000
#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], cc[3][N], cc_[3][N], hh[3][N], n;
int *vv;
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 (vv[ii[j]] == vv[i_])
j++;
else if (vv[ii[j]] < vv[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;
}
}
void update(long long *ft, int i, int n, int x) {
while (i < n) {
ft[i] += x;
i |= i + 1;
}
}
long long query(long long *ft, int i) {
long long x = 0;
while (i >= 0) {
x += ft[i];
i &= i + 1, i--;
}
return x;
}
long long ftk[3][N], fts[3][N];
int count(int g, long long c) {
int lower = -1, upper = n;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (cc_[g][h] <= c)
lower = h;
else
upper = h;
}
return query(ftk[g], lower);
}
long long sum(int g, long long c) {
int lower = -1, upper = n;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (cc_[g][h] <= c)
lower = h;
else
upper = h;
}
return query(fts[g], lower);
}
int main() {
static int ww[N], ii[N * 2];
int k, g, h, i, i_, x, kl, km, kr;
long long w, lower, upper, c, 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];
cc[2][i] = ww[i] + xx[i << 1 | 0];
}
for (g = 0; g < 3; g++) {
for (i = 0; i < n; i++)
ii[i] = i;
vv = cc[g], sort(ii, 0, n);
for (h = 0; h < n; h++) {
i = ii[h];
cc_[g][h] = cc[g][i];
hh[g][i] = h;
}
}
for (i = 0; i < n * 2; i++)
ii[i] = i;
vv = xx, sort(ii, 0, n * 2);
for (i = 0; i < n; i++)
update(ftk[2], hh[2][i], n, 1), update(fts[2], hh[2][i], n, cc_[2][hh[2][i]]);
ans = INF;
for (h = 0; h < n * 2; h++) {
i_ = ii[h], i = i_ >> 1, x = xx[i_];
if ((i_ & 1) == 0) {
update(ftk[2], hh[2][i], n, -1), update(fts[2], hh[2][i], n, -cc_[2][hh[2][i]]);
update(ftk[1], hh[1][i], n, 1), update(fts[1], hh[1][i], n, cc_[1][hh[1][i]]);
} else {
update(ftk[1], hh[1][i], n, -1), update(fts[1], hh[1][i], n, -cc_[1][hh[1][i]]);
update(ftk[0], hh[0][i], n, 1), update(fts[0], hh[0][i], n, cc_[0][hh[0][i]]);
}
lower = -1, upper = (long long) X * 4 + 1;
while (upper - lower > 1) {
c = (lower + upper) / 2;
if (count(0, c - x) + count(1, c) + count(2, c + x) <= k)
lower = c;
else
upper = c;
}
c = lower;
kl = count(0, c - x), km = count(1, c), kr = count(2, c + x);
ans = min(ans, sum(0, c - x) + (long long) x * kl + sum(1, c) + sum(2, c + x) - (long long) x * kr + (c + 1) * (k - kl - km - kr) - w);
}
printf("%lld\n", ans);
return 0;
}
