#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[N * 3];
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 data[N * 3 + 1][5], u_, l_, r_; long long ss[N * 3 + 1];
int node(int i) {
static int _ = 1;
data[_][0] = rand_();
data[_][3] = i;
data[_][4] = 1, ss[_] = cc[i];
return _++;
}
void pul(int u) {
int l = data[u][1], r = data[u][2];
data[u][4] = data[l][4] + 1 + data[r][4];
ss[u] = ss[l] + cc[data[u][3]] + ss[r];
}
void split(int u, int i) {
int c;
if (u == 0) {
u_ = l_ = r_ = 0;
return;
}
c = cc[data[u][3]] != cc[i] ? (cc[data[u][3]] < cc[i] ? -1 : 1) : data[u][3] - i;
if (c < 0) {
split(data[u][2], i);
data[u][2] = l_, l_ = u;
} else if (c > 0) {
split(data[u][1], i);
data[u][1] = r_, r_ = u;
} else {
u_ = u, l_ = data[u][1], r_ = data[u][2];
data[u][1] = data[u][2] = 0;
}
pul(u);
}
int merge(int u, int v) {
if (u == 0)
return v;
if (v == 0)
return u;
if (data[u][0] < data[v][0]) {
data[u][2] = merge(data[u][2], v), pul(u);
return u;
} else {
data[v][1] = merge(u, data[v][1]), pul(v);
return v;
}
}
int tr_add(int u, int i) {
split(u, i);
return merge(merge(l_, node(i)), r_);
}
int tr_remove(int u, int i) {
split(u, i);
return merge(l_, r_);
}
int count(int u, long long c) {
int k;
k = 0;
while (u)
if (cc[data[u][3]] <= c)
k += data[u][4] - data[data[u][2]][4], u = data[u][2];
else
u = data[u][1];
return k;
}
long long sum(int u, long long c) {
long long s;
s = 0;
while (u)
if (cc[data[u][3]] <= c)
s += ss[u] - ss[data[u][2]], u = data[u][2];
else
u = data[u][1];
return s;
}
int main() {
static int ww[N], ii[N * 2];
int n, k, h, i, i_, ul, um, ur, 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[i * 3 + 0] = ww[i] + xx[i << 1 | 0];
cc[i * 3 + 1] = ww[i];
cc[i * 3 + 2] = ww[i] - xx[i << 1 | 1];
}
for (i = 0; i < n * 2; i++)
ii[i] = i;
sort(ii, 0, n * 2);
ul = 0, um = 0, ur = 0;
for (i = 0; i < n; i++)
ur = tr_add(ur, i * 3 + 0);
ans = INF;
for (h = 0; h < n * 2; h++) {
i_ = ii[h], i = i_ >> 1, x = xx[i_];
if ((i_ & 1) == 0) {
ur = tr_remove(ur, i * 3 + 0);
um = tr_add(um, i * 3 + 1);
} else {
um = tr_remove(um, i * 3 + 1);
ul = tr_add(ul, i * 3 + 2);
}
lower = -1, upper = (long long) X * 4 + 1;
while (upper - lower > 1) {
c = (lower + upper) / 2;
if (count(ul, c - x) + count(um, c) + count(ur, c + x) <= k)
lower = c;
else
upper = c;
}
c = lower;
kl = count(ul, c - x), km = count(um, c), kr = count(ur, c + x);
ans = min(ans, sum(ul, c - x) + (long long) x * kl + sum(um, c) + sum(ur, c + x) - (long long) x * kr + (c + 1) * (k - kl - km - kr) - w);
}
printf("%lld\n", ans);
return 0;
}
