#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define endl '\n'
#pragma GCC optimize("Ofast")
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair < int, int >;
using pll = pair < ll, ll >;
const ll INF = 2e18;
const ll DIM = 400007;
const ll DIMQ = 2007;
const ld PI = 3.1415926535;
const int mod = 998244353;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef IloveCP
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n, k;
cin >> n >> k;
vector < vector < pll > > a(4);
vector < ll > c(n);
for(int i = 0; i < n; i++) {
ll t, x, y;
cin >> t >> x >> y >> c[i];
t--;
if(t < 2) a[t].push_back({x, i});
else a[t].push_back({y, i});
}
vector < vector < ll > > x(a[0].size() + a[2].size(), vector < ll >(a[1].size() + a[3].size(), INF));
for(int t = 0; t < 4; t++) {
sort(a[t].begin(), a[t].end());
}
for(int i = 0; i < a[0].size(); i++) {
for(int j = 0; j < a[1].size(); j++) {
if(a[0][i].first >= a[1][j].first) {
x[i][j] = c[a[0][i].second] + c[a[1][j].second];
}
}
}
for(int i = 0; i < a[2].size(); i++) {
for(int j = 0; j < a[3].size(); j++) {
if(a[2][i].first >= a[3][j].first) {
x[i + a[0].size()][j + a[1].size()] = c[a[2][i].second] + c[a[3][j].second];
}
}
}
vector < vector < ll > > curr = x;
while(k > 1) {
vector < vector < ll > > mi = curr;
for(int i = 0; i < mi.size(); i++) {
for(int j = 0; j < mi[i].size(); j++) {
if(i != 0) mi[i][j] = min(mi[i][j], mi[i - 1][j]);
if(j != 0) mi[i][j] = min(mi[i][j], mi[i][j - 1]);
}
}
for(int i = 0; i < curr.size(); i++) {
for(int j = 0; j < curr[i].size(); j++) {
if(i == 0 || j == 0) {
curr[i][j] = INF;
continue;
}
curr[i][j] = mi[i - 1][j - 1] + x[i][j];
curr[i][j] = min(curr[i][j], INF);
}
}
k--;
}
ll res = INF;
for(int i = 0; i < curr.size(); i++) {
for(int j = 0; j < curr[i].size(); j++) {
res = min(res, curr[i][j]);
}
}
cout << (res == INF ? -1 : res) << endl;
return 0;
}
