#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <memory.h>
#include <cmath>
#include <array>

using namespace std;

void re(int& x);

template<class T, class... Ts> void re(T& t, Ts&... ts);

void pr(long long x);

void pr(const char *x);

void ps();
template<class T, class... Ts> void ps(const T& t, const Ts&... ts);

#ifdef FFDBG

#else
#define dbg(x...) dsfdsfsdfasd
#endif

typedef long long ll;

#define rep(i, a, b) for(int i = a; i < (b); ++i)

int n, x;
long long tgt = 0;

struct ex {
    int l, r, b;
} exam[110000];

long long score(const ex& a, long long h) {
    long long sc = a.l * 1ll * min(h, (ll)a.b);
    sc += a.r * 1ll * max(0LL, h-a.b);
    return sc;
}

bool check(long long hrs) {
    int full = hrs / x;
    int rem = hrs % x; 

    long long sc = 0;
    rep(i,0,full) sc += score(exam[i], x);
    long long best = sc;

    rep(i,full,n) best = max(best, sc + score(exam[i], rem));
    
    if (full < n) {
        sc += score(exam[full], x);
        rep(i,0,full) best = max(best, sc - score(exam[i], x) + score(exam[i],rem));
    }
    
    return best >= tgt;
}

void solve()
{
    re(n,x);
    rep(i,0,n) re(exam[i].b, exam[i].l, exam[i].r);

    rep(i,0,n) tgt += exam[i].l * 1ll * exam[i].b;

    sort(exam, exam+n, [](const ex& a, const ex& b) {
        return score(a,x) > score(b,x);
    });

    long long st = 0, ed = n*1ll*x;
    while (st < ed) {
        long long md = (st+ed)/2;
        if (check(md)) ed = md;
        else st = md+1;
    } 

    ps(st);
}

int main() {

    solve();
}

void re(int& x) { scanf("%d", &x); }

template<class T, class... Ts> void re(T& t, Ts&... ts) { 
    re(t); re(ts...); 
}

void pr(long long x) { printf("%lld", x); }

void pr(const char *x) { printf("%s", x); }

void ps() { pr("\n"); }
template<class T, class... Ts> void ps(const T& t, const Ts&... ts) { 
    pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); 
}


// Program Name: Minimum Spanning Tree
// Written by: by_sknight
// Date: 2019/4/27
#include <bits/stdc++.h>
using namespace std;
#define MAX 105
#define INFTY INT_MAX
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n, G[MAX][MAX];

int prim() {
    int d[MAX], p[MAX], color[MAX];
    int u, minv;
    for (int i = 0; i < n; i++) {
        d[i] = INFTY;
        p[i] = -1;
        color[i] = WHITE;
    }

    d[0] = 0;

    while (1) {
        u = -1;
        minv = INFTY;
        for (int i = 0; i < n; i++) {
            if (color[i] != BLACK && d[i] < minv) {
                minv = d[i];
                u = i;
            }
        }
        if (u == -1) 
            break;
        color[u] = BLACK;
        for (int v = 0; v < n; v++) {
            if (color[v] != BLACK && G[u][v] < d[v]) {
                d[v] = G[u][v];
                p[v] = u;
                color[v] = GRAY;
            }
        }
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (p[i] != -1) {
            sum += d[i];
        }
    }
    return sum;
}

int main(void) {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int k;
            cin >> k;
            G[i][j] = (k == -1 ? INFTY : k);
        }
    }

    int sum = prim();

    cout << sum << endl;
}
