- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define endl "\n"
- #define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
- #define ALL(x) x.begin(),x.end()
- #define SORT(x) sort(ALL(x))
- #define FOR(a,b,c) for(ll (a)= (b);(a)<(c);++(a))
- #define REP(a,b) FOR(a,0,b)
- #define mp make_pair
- #define pb push_back
- #define pll pair<ll,ll>
- #define pii pair<int,int>
- #define vl vector<ll>
- #define vi vector<int>
- #define f first
- #define s second
- #define yy cout<<"YES"<<endl;return
- #define nn cout<<"NO"<<endl;return
- #define minus1 cout<<-1<<endl;return
- #define rd(a,x) REP(i,x)cin >> a[i]
- int ttt = 1, case_ = 0;
- ll n, m, k, p;
- template <class myType>
- void print_arr(myType &arr, ll L, string sep){
- REP(i,L){ cout << arr[i] << (i < L-1 ? sep : "\n"); }
- return; }
- /*
- We're interested fundamentally in the top M values of (a[i] - b[i]) added to all the values of b[i] between each two stops
- We have a seat of people sitting, and a set of people standing
- Put everyone who gets on into seats
- Move everyone better than them who is standing into seats
- Move anyone not in the top M out of a seat
- Move anyone with diff < 0 out of a seat
- */
- void solve() {
- cin >> n >> m >> p;
- vector<vl> people;
- REP(i, n) {
- ll a, b, l, r;
- cin >> a >> b >> l >> r;
- people.pb({l, 1, a, b});
- people.pb({r, -1, a, b});
- }
- SORT(people);
- multiset<ll> seats, stood;
- int j = 0;
- ll curr_b = 0, curr_diff = 0;
- ll ans = 0;
- FOR(i, 1, p) {
- while (j < 2*n && people[j][0] == i) {
- if (people[j][1] == 1) {
- // person is joining the bus
- ll a = people[j][2], b = people[j][3];
- ll diff = a - b;
- seats.insert(diff);
- curr_diff += diff;
- curr_b += b;
- }
- else {
- // person is leaving the bus
- ll a = people[j][2], b = people[j][3];
- ll diff = a - b;
- auto it = stood.find(diff);
- if (it != stood.end()) {
- stood.erase(stood.lower_bound(diff));
- }
- else {
- seats.erase(seats.lower_bound(diff));
- curr_diff -= diff;
- }
- curr_b -= b;
- }
- j++;
- }
- // I've put everyon
- while (seats.size() > m) {
- auto it = seats.begin();
- auto x = *it;
- seats.erase(seats.lower_bound(x));
- stood.insert(x);
- curr_diff -= x;
- }
- while (seats.size() < m && stood.size() > 0 && *stood.rbegin() > 0) {
- auto it = stood.rbegin();
- seats.insert(*it);
- curr_diff += *it;
- stood.erase(stood.lower_bound(*it));
- }
- while (seats.size() > 0 && stood.size() > 0 && *seats.begin() < *stood.rbegin() && *stood.rbegin() > 0) {
- auto it = stood.rbegin();
- auto it2 = seats.begin();
- auto x = *it;
- auto y = *it2;
- stood.erase(stood.lower_bound(x));
- seats.erase(seats.lower_bound(y));
- stood.insert(y);
- seats.insert(x);
- curr_diff += x - y;
- }
- while (seats.size() > 0 && *seats.begin() < 0) {
- auto it = seats.begin();
- auto x = *it;
- seats.erase(seats.lower_bound(x));
- stood.insert(x);
- curr_diff -= x;
- }
- ans += curr_b + curr_diff;
- }
- cout << ans << endl;
- return;
- }
- int main() {
- quick;
- //cin >> ttt;
- while (ttt--) solve();
- return 0;
- }