#include "meeting.h"
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
namespace {
    ll n,k;
    const ll MAXN = 2.5e3;
    const ll INF = 1e18;
    ll s[MAXN+100];
    ll e[MAXN+100];
    ll w[MAXN+100];
    vector <ll> val;
    ll dp[2 * MAXN + 100];
    ll solve(){
        for (ll i = 1;i <= n;i ++){
            val.push_back(s[i]);
            val.push_back(e[i]);
        }
        sort(val.begin(),val.end());
        val.resize(unique(val.begin(),val.end())-val.begin());
        for (ll i = 1;i <= n;i ++){
            s[i] = lower_bound(val.begin(),val.end(),s[i])-val.begin()+1;
            e[i] = lower_bound(val.begin(),val.end(),e[i])-val.begin()+1;
        }
        vector <ll> rg;
        for (ll i = 1;i <= sz(val);i ++)dp[i] = INF;
        for (ll i = 1;i <= n;i ++)rg.push_back(i);
        sort(rg.begin(),rg.end(),[](ll x,ll y){return e[x] < e[y];});
//        for (ll i = 1;i <= n;i ++){
//            cout<<s[i]<<' '<<e[i]<<endl;
//        }
        dp[0] = 0;
        for (ll i = 0;i <= sz(val);i ++){
            ll cost = 0;
//            cout<<i<<' '<<dp[i]<<endl;
            priority_queue <ll,vector <ll>,greater <> > pq;
            for (ll j = i + 1,ptr = 0;j <= 2*n;j ++){
                while (ptr<sz(rg) && e[rg[ptr]] <= j){
//                    cout<<"WOW "<<ptr<<' '<<rg[ptr]<<' '<<e[rg[ptr]]<<endl;
                    cost += (e[rg[ptr]] >= i + 1 && s[rg[ptr]] <= i) * w[rg[ptr]];
                    if (s[rg[ptr]] > i)pq.push(w[rg[ptr]]);
                    while (sz(pq)>k){
                        cost+=pq.top();
                        pq.pop();
                    }
                    ptr++;
                }
//                cout<<i<<' '<<j<<' '<<dp[i]<<' '<<cost<<' '<<cnt<<endl;
                dp[j] = min(dp[j],dp[i]+cost);
            }
        }
        return dp[sz(val)];
    }
}
long long min_charge(int K, std::vector<int> S, std::vector<int> E, std::vector<int> W) {
    n = sz(S);
    k = K;
    for (ll i = 1;i <= n;i ++)s[i] = S[i-1],e[i] = E[i-1],w[i] = W[i-1];
	return solve();
}