#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
#define ff first
#define ss second
#define pi pair<ll, ll>
#define pll pair<long long, long long>
#define vi vector<ll>
#define vll vector<long long>
#define vpi vector<pair<ll,ll>>
#define vpll vector<pair<long long, long long>>
#define pb push_back
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)(x).size()
#define forall(it,x) for(auto& it:(x))
#define mp make_pair
pi operator+(pi a, pi b) { return mp(a.ff+b.ff, a.ss+b.ss); }
pi operator-(pi a, pi b) { return mp(a.ff-b.ff, a.ss-b.ss); }
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll inf = 1e18;
struct Cow {
ll t, x, c; // 1 - closing, 2 - opening
friend bool operator<(Cow a, Cow b) {
if(a.x != b.x) return a.x < b.x;
return a.t > b.t;
}
};
pi solve(vector<Cow> cows, ll alpha) {
ll cost = 0, amount = 0;
priority_queue<ll, vector<ll>, greater<ll>> open, closed;
for(auto[t,x,c] : cows) {
if(t==1) {
ll v1 = (closed.size() ? closed.top() : inf) + c;
ll v2 = (open.size() ? open.top() : inf) + c;
if(v1 > 0 && v2 > 0) continue;
if(v2 <= v1) {
cost += v2;
amount++;
closed.push(-c);
open.pop();
} else {
cost += v1;
closed.pop();
closed.push(-c);
}
} else {
open.push(c - alpha);
}
}
return mp(cost, amount);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n, K;
cin >> n >> K;
vector<Cow> c1, c2;
for(ll i=0; i<n; ++i) {
ll t,x,y,c;
cin >> t >> x >> y >> c;
if(t <= 2) c1.pb({t,x,c});
else c2.pb({t-2,y,c});
}
sort(all(c1));
sort(all(c2));
ll lo = 0;
ll hi = (ll)1e16;
ll res = -1;
while(lo <= hi) {
ll alpha = (lo+hi)/2;
auto[cost1, a1] = solve(c1, alpha);
auto[cost2, a2] = solve(c2, alpha);
ll cost = cost1+cost2;
ll a = a1+a2;
if(a < K) lo = alpha + 1;
else {
hi = alpha-1;
res = cost + a * alpha;
}
}
cout << res << "\n";
return 0;
}
