#include "bits/stdc++.h"
using namespace std;
const int N = 105;
const long long inf = -1e15;
int n , m;
int a[N] , b[N] , c[N];
long long dist[N];
int pre[N];
int cap[N][N];
int cst[N][N];
bool solve(vector < pair < int , int > > &v){
for(int i = 0 ; i <= n + 2 ; ++i){
dist[i] = inf;
pre[i] = -1;
}
dist[0] = 0;
pre[0] = 0;
for(int i = 0 ; i <= n + 2 ; ++i){
for(auto it : v){
int a = it.first;
int b = it.second;
if(cap[a][b] > 0){
if(dist[a] != inf){
if(dist[b] < dist[a] + cst[a][b]){
dist[b] = dist[a] + cst[a][b];
pre[b] = a;
}
}
}
}
}
return (dist[n + 2] != inf);
}
bool check(int val){
memset(cap , 0 , sizeof(cap));
memset(cst , 0 , sizeof(cst));
vector < pair < int , int > > v;
v.clear();
cap[0][1] = val;
v.emplace_back(make_pair(0 , 1));
v.emplace_back(make_pair(1 , 0));
for(int i = 1 ; i <= n ; ++i){
cap[1][i + 1] = (b[i] - a[i]) / c[i];
v.emplace_back(make_pair(1 , i + 1));
cst[1][i + 1] = c[i];
cst[i + 1][1] = -c[i];
v.emplace_back(make_pair(i + 1 , 1));
cap[i + 1][n + 2] = (b[i] - a[i]) / c[i];
v.emplace_back(make_pair(i + 1 , n + 2));
v.emplace_back(make_pair(n + 2 , i + 1));
}
long long ans = 0;
for(int i = 1 ; i <= n ; ++i){
ans += a[i];
}
while(solve(v)){
int node = n + 2;
int flow = val;
while(node){
flow = min(flow , cap[pre[node]][node]);
node = pre[node];
}
node = n + 2;
while(node){
ans += cst[pre[node]][node] * flow;
cap[pre[node]][node] -= flow;
cap[node][pre[node]] += flow;
node = pre[node];
}
}
return ans >= m * n;
}
int main(){
scanf("%d %d" , &n , &m);
for(int i = 1 ; i <= n ; ++i){
scanf("%d %d %d" , a + i , b + i , c + i);
}
int l = 1;
int r = 1e4 + 4;
if(!check(r)){
printf("-1\n");
}
else{
while(l < r){
int mid = l + r >> 1;
if(check(mid)){
r = mid;
}
else{
l = mid + 1;
}
}
printf("%d\n" , l);
}
}
I2luY2x1ZGUgImJpdHMvc3RkYysrLmgiCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNvbnN0IGludCBOID0gMTA1Owpjb25zdCBsb25nIGxvbmcgaW5mID0gLTFlMTU7CmludCBuICwgbTsKaW50IGFbTl0gLCBiW05dICwgY1tOXTsKbG9uZyBsb25nIGRpc3RbTl07CmludCBwcmVbTl07CmludCBjYXBbTl1bTl07CmludCBjc3RbTl1bTl07CmJvb2wgc29sdmUodmVjdG9yIDwgcGFpciA8IGludCAsIGludCA+ID4gJnYpewogICAgZm9yKGludCBpID0gMCA7IGkgPD0gbiArIDIgOyArK2kpewogICAgICAgIGRpc3RbaV0gPSBpbmY7CiAgICAgICAgcHJlW2ldID0gLTE7CiAgICB9CiAgICBkaXN0WzBdID0gMDsKICAgIHByZVswXSA9IDA7CiAgICBmb3IoaW50IGkgPSAwIDsgaSA8PSBuICsgMiA7ICsraSl7CiAgICAgICAgZm9yKGF1dG8gaXQgOiB2KXsKICAgICAgICAgICAgaW50IGEgPSBpdC5maXJzdDsKICAgICAgICAgICAgaW50IGIgPSBpdC5zZWNvbmQ7CiAgICAgICAgICAgIGlmKGNhcFthXVtiXSA+IDApewogICAgICAgICAgICAgICAgaWYoZGlzdFthXSAhPSBpbmYpewogICAgICAgICAgICAgICAgICAgIGlmKGRpc3RbYl0gPCBkaXN0W2FdICsgY3N0W2FdW2JdKXsKICAgICAgICAgICAgICAgICAgICAgICAgZGlzdFtiXSA9IGRpc3RbYV0gKyBjc3RbYV1bYl07CiAgICAgICAgICAgICAgICAgICAgICAgIHByZVtiXSA9IGE7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIChkaXN0W24gKyAyXSAhPSBpbmYpOwp9CmJvb2wgY2hlY2soaW50IHZhbCl7CiAgICBtZW1zZXQoY2FwICwgMCAsIHNpemVvZihjYXApKTsKICAgIG1lbXNldChjc3QgLCAwICwgc2l6ZW9mKGNzdCkpOwogICAgdmVjdG9yIDwgcGFpciA8IGludCAsIGludCA+ID4gdjsKICAgIHYuY2xlYXIoKTsKICAgIGNhcFswXVsxXSA9IHZhbDsKICAgIHYuZW1wbGFjZV9iYWNrKG1ha2VfcGFpcigwICwgMSkpOwogICAgdi5lbXBsYWNlX2JhY2sobWFrZV9wYWlyKDEgLCAwKSk7CiAgICBmb3IoaW50IGkgPSAxIDsgaSA8PSBuIDsgKytpKXsKICAgICAgICBjYXBbMV1baSArIDFdID0gKGJbaV0gLSBhW2ldKSAvIGNbaV07CiAgICAgICAgdi5lbXBsYWNlX2JhY2sobWFrZV9wYWlyKDEgLCBpICsgMSkpOwogICAgICAgIGNzdFsxXVtpICsgMV0gPSBjW2ldOwogICAgICAgIGNzdFtpICsgMV1bMV0gPSAtY1tpXTsKICAgICAgICB2LmVtcGxhY2VfYmFjayhtYWtlX3BhaXIoaSArIDEgLCAxKSk7CiAgICAgICAgY2FwW2kgKyAxXVtuICsgMl0gPSAoYltpXSAtIGFbaV0pIC8gY1tpXTsKICAgICAgICB2LmVtcGxhY2VfYmFjayhtYWtlX3BhaXIoaSArIDEgLCBuICsgMikpOwogICAgICAgIHYuZW1wbGFjZV9iYWNrKG1ha2VfcGFpcihuICsgMiAsIGkgKyAxKSk7CiAgICB9CiAgICBsb25nIGxvbmcgYW5zID0gMDsKICAgIGZvcihpbnQgaSA9IDEgOyBpIDw9IG4gOyArK2kpewogICAgICAgIGFucyArPSBhW2ldOwogICAgfQogICAgd2hpbGUoc29sdmUodikpewogICAgICAgIGludCBub2RlID0gbiArIDI7CiAgICAgICAgaW50IGZsb3cgPSB2YWw7CiAgICAgICAgd2hpbGUobm9kZSl7CiAgICAgICAgICAgIGZsb3cgPSBtaW4oZmxvdyAsIGNhcFtwcmVbbm9kZV1dW25vZGVdKTsKICAgICAgICAgICAgbm9kZSA9IHByZVtub2RlXTsKICAgICAgICB9CiAgICAgICAgbm9kZSA9IG4gKyAyOwogICAgICAgIHdoaWxlKG5vZGUpewogICAgICAgICAgICBhbnMgKz0gY3N0W3ByZVtub2RlXV1bbm9kZV0gKiBmbG93OwogICAgICAgICAgICBjYXBbcHJlW25vZGVdXVtub2RlXSAtPSBmbG93OwogICAgICAgICAgICBjYXBbbm9kZV1bcHJlW25vZGVdXSArPSBmbG93OwogICAgICAgICAgICBub2RlID0gcHJlW25vZGVdOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBhbnMgPj0gbSAqIG47Cn0KaW50IG1haW4oKXsKICAgIHNjYW5mKCIlZCAlZCIgLCAmbiAsICZtKTsKICAgIGZvcihpbnQgaSA9IDEgOyBpIDw9IG4gOyArK2kpewogICAgICAgIHNjYW5mKCIlZCAlZCAlZCIgLCBhICsgaSAsIGIgKyBpICwgYyArIGkpOwogICAgfQogICAgaW50IGwgPSAxOwogICAgaW50IHIgPSAxZTQgKyA0OwogICAgaWYoIWNoZWNrKHIpKXsKICAgICAgICBwcmludGYoIi0xXG4iKTsKICAgIH0KICAgIGVsc2V7CiAgICAgICAgd2hpbGUobCA8IHIpewogICAgICAgICAgICBpbnQgbWlkID0gbCArIHIgPj4gMTsKICAgICAgICAgICAgaWYoY2hlY2sobWlkKSl7CiAgICAgICAgICAgICAgICByID0gbWlkOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2V7CiAgICAgICAgICAgICAgICBsID0gbWlkICsgMTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBwcmludGYoIiVkXG4iICwgbCk7CiAgICB9Cn0K