#include <algorithm>
#include <iostream>
#include <limits>
#include <set>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
using ll = long long ;
const ll inf = (1ll << 58);
struct kakko{
long long cost;
ll idx;
kakko() : cost(inf),idx(-1){}
kakko(ll c,ll i):cost(c),idx(i){}
kakko operator+(ll add){
if(cost == inf) return kakko(inf, -1);
return kakko(cost + add, idx);
}
bool operator<(kakko& k){
return (cost < k.cost);
}
};
struct type{
kakko L,R,pair_L,pair_R;
type(){}
type(ll idx,ll t,ll val){
if(t == 0) L = kakko(val, idx); // (
else R = kakko(val, idx); // )
}
ll cost(){
if(pair_L.cost == inf || pair_R.cost == inf) return inf;
return pair_L.cost + pair_R.cost;
}
};
type merge(type &a, type &b, bool fL = true, bool fR = true){
type res;
res.L = b.L;
res.R = a.R;
if(res.cost() > a.cost()){
res.pair_L = a.pair_L;
res.pair_R = a.pair_R;
}
if(res.cost() > b.cost()){
res.pair_L = b.pair_L;
res.pair_R = b.pair_R;
}
if(res.cost() > a.L.cost + b.R.cost){
res.pair_L = a.L;
res.pair_R = b.R;
}
if(fR && a.L<res.L) res.L = a.L;
if(fL && b.R<res.R) res.R = b.R;
return res;
}
struct Node{
ll min_cap;
type rev_use_min, rev_not_use_min,node;
Node(): min_cap(0){}
Node(ll idx, ll t, ll val): min_cap(0){
//rev_not_use_min = type(idx, t^1, val);
rev_use_min = type(idx, t^1, val);
node = type(idx, t, val);
}
};
struct Lazy_Segment_Tree{
ll n;
vector<Node> dat;
vector<ll> lazy;
Lazy_Segment_Tree(const vector<pair<ll, ll>>& data){
ll size = data.size();
n = 1;
while(n < size) n *= 2;
dat.resize(2*n);
lazy.assign(2*n, 0);
for(ll i=0; i<size; ++i) dat[i+n] = Node(i, data[i].first, data[i].second);
for(ll i=n-1; i>=1; --i) dat[i] = f(dat[2*i], dat[2*i+1]);
}
Node f(Node& a, Node& b){
Node res;
res.min_cap = min(a.min_cap, b.min_cap);
bool fL = (a.min_cap != res.min_cap);
bool fR = (b.min_cap != res.min_cap);
type L = fL ? a.rev_use_min : a.rev_not_use_min;
type R = fR ? b.rev_use_min : b.rev_not_use_min;
res.node = merge(a.node,b.node);
res.rev_not_use_min = merge(L, R, fL, fR);
res.rev_use_min = merge(a.rev_use_min, b.rev_use_min);
return res;
}
void apply(ll i, ll val){
dat[i].min_cap += val;
lazy[i] += val;
}
void eval(ll i){
if(lazy[i] == 0) return;
apply(2*i, lazy[i]);
apply(2*i+1, lazy[i]);
lazy[i] = 0;
}
void update(ll a, ll b, ll val, ll l, ll r, ll i){
if(b<=l || r<=a) return;
if(a<=l && r<=b){
apply(i, val);
return;
}
eval(i);
update(a, b, val, l, (l + r)/2, 2*i);
update(a, b, val, (l + r)/2, r, 2*i+1);
dat[i] = f(dat[2*i], dat[2*i+1]);
}
void disable(ll idx, ll l, ll r, ll i){
if(l + 1 == r){
dat[i].node = type();
dat[i].rev_use_min = type();
dat[i].rev_not_use_min = type();
return;
}
eval(i);
ll mid = (l + r)/2;
if(idx < mid) disable(idx, l, mid, 2*i);
else disable(idx, mid, r, 2*i + 1);
dat[i] = f(dat[2*i], dat[2*i+1]);
}
void update(ll a, ll b, ll val){
update(a, b, val, 0, n, 1);
}
void use(ll idx){
disable(idx, 0, n, 1);
}
tuple<ll,ll,ll> min_cost(){
ll kc = (dat[1].min_cap?min(dat[1].rev_use_min.cost(),dat[1].rev_not_use_min.cost()):dat[1].rev_not_use_min.cost());
if(dat[1].node.cost() <= kc) return{dat[1].node.cost(),dat[1].node.pair_L.idx,dat[1].node.pair_R.idx};
if(dat[1].min_cap > 0 && dat[1].rev_use_min.cost()<dat[1].rev_not_use_min.cost()) return {dat[1].rev_use_min.cost(),dat[1].rev_use_min.pair_R.idx,dat[1].rev_use_min.pair_L.idx};
return {dat[1].rev_not_use_min.cost(),dat[1].rev_not_use_min.pair_R.idx,dat[1].rev_not_use_min.pair_L.idx};
}
};
vector<ll> solve(ll K,vector<tuple<ll,ll,ll>>& S){
vector<ll> cost = {0};
ll nc = 0;
sort(S.begin(), S.end());
vector<pair<ll, ll>> data;
for(auto val : S){
ll t;
ll cost;
tie(ignore, t, cost) = val;
data.emplace_back(t, cost);
}
if(data.empty()){
for(ll i = 0; i<K; ++i) cost.push_back(inf);
return cost;
}
Lazy_Segment_Tree seg(data);
for(ll i = 0; i<K; ++i){
ll dc,L,R;
tie(dc,L,R) = seg.min_cost();
if(dc >= inf){
cost.push_back(inf);
continue;
}
nc += dc;
cost.push_back(nc);
seg.use(L);
seg.use(R);
if(L < R)seg.update(L, R, 1);
else seg.update(R, L, -1);
}
return cost;
}
int main(){
ll N, K;
cin >> N >> K;
vector<vector<tuple<ll,ll,ll>>> D(2);
for(ll i = 0; i<N; ++i){
ll T, X, Y;
ll C;
cin >> T >> X >> Y >> C;
if(T <= 2) D[(T-1)/2].emplace_back(X, T%2, C);
else D[(T-1)/2].emplace_back(Y, T%2, C);
}
vector<ll> cost_X = solve(K,D[0]), cost_Y = solve(K,D[1]);
ll ans = inf;
for(ll i = 0; i<=K; ++i){
ans = min(ans, cost_X[i] + cost_Y[K-i]);
}
cout << (ans == inf ? -1:ans) << endl;
return 0;
}
