#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define MOD 1000000007
#define cey ce("Yes")
#define cen ce("No")
#define ceY ce("YES")
#define ceN ce("NO")

ll dp2[150000][20];
ll cost[20][20];// wa―シャルフロイド
int main()
{
	int N;
	cin >> N;

	vector<tuple<int, int, int>> B;
	fx(N) {
		int a, b, c;
		cin >> a >> b >> c;
		B.push_back(make_tuple(a, b, c));
	}

	fx(N) {
		fy(N) {
			cost[x + 1][y + 1] = abs(get<0>(B[x]) - get<0>(B[y])) + abs(get<1>(B[x]) - get<1>(B[y])) + max(0, get<2>(B[y]) - get<2>(B[x]));
		}
	}

	//fy(N) {
	//	fx(N) {
	//		fz(N) {
	//			cost[x+1][z + 1] = min(cost[x + 1][z + 1], cost[x + 1][y + 1] + cost[y + 1][z + 1]);
	//		}
	//	}

	//}


	fx(150000) {
		fy(N) {
			dp2[x][y+1] = LLONG_MAX;
		}

	}

	dp2[1][1] = 0;

	for (int y = 1; y < (1 << N); y += 2) {
		fx(N) {
			if (((1 << x) & y) == 0) { continue; }
			if (dp2[y][x + 1] == LLONG_MAX) { continue; }
			fz(N) {   // 増やし先
				if (((1 << z) & y) != 0) { continue; }
				fw(N) {
					if (((1 << w) & y) == 0) { continue; }
					dp2[y | (1 << z)][z+1] = min(dp2[y | (1 << z)][z+1], dp2[y][x+1] + cost[x + 1][w + 1] + cost[w + 1][z + 1]);
				}
			}
		}
	}
	
	ll ans = LLONG_MAX;
	fx(N) {
		//if (dp2[(1 << N) - 1][x + 1] == LLONG_MAX) { continue; }
		if (dp2[(1 << N) - 1][x + 1] < 0) { continue; }
		ans = min(ans, dp2[(1 << N) - 1][x + 1] + cost[x + 1][1]);
	}
	ce(ans)	


    return 0;
}


#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define PI 3.14159265358979323846264338327950L


struct times{
    bool start;
    ll time = 0;
    ll value = 0;
};

int N,C;
priority_queue<pair<int,times*>> q ;

void solve(){
   
    cin >> N>> C;

    ll a,b,c;
    for (int i = 0; i < N; i++)
    {
        cin >> a >> b >> c;
        times* t = new times();
        t->start = true;
        t->time = a;
        t->value = c;
        q.push(make_pair(-a*2,t));

        times* f = new times();
        f->start = false;
        f->time = b;
        f->value = c;
        q.push(make_pair(-b*2-1,f));
    }
    
    ll ans = 0;
    ll cost = 0;
    ll topay = 0;
    ll pos = q.top().second->start;
    for (int i = 0; i < 2*N; i++)
    {
        auto e = q.top();
        q.pop();

        

        topay = (cost > C) ? C : cost;

        if(e.second->start){
            cost += e.second->value;
            
            ans += (e.second->time - pos )* topay;
            pos = e.second->time;
        } 
        else{
            if(pos <= e.second->time){
                ans += (e.second->time - pos +1 )* topay;
                pos = e.second->time +1;
            }
            cost -= e.second->value;
        } 

    }
    
    cout << ans<< endl;

}





int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}
