#include "meeting.h"
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
const ll inf=1e18;

struct BIT
{
    ll n;
    vector <ll> bit;
    BIT (ll n): n(n) {bit.assign(n+5, 0);}

    void upd(ll i, ll val)
    {
        for (++i; i<=n; i+=i&(-i))
            bit[i]+=val;
    }
    void update(ll l, ll r, ll val) {
        upd(l, val), upd(r+1, -val);}

    ll query(ll i) 
    {
        ll ans=0;
        for (++i; i; i-=i&(-i))
            ans+=bit[i];
        return ans;
    }
};

long long min_charge(int K, vector<int> s, vector<int> e, vector<int> w) 
{
    ll n=sz(w);
    vector <ll> num;
    for (ll i=0; i<n; i++)
        num.pb(s[i]), num.pb(e[i]);
    sort(num.begin(), num.end());
    num.resize(unique(num.begin(), num.end())-num.begin());
    ll k=sz(num);
    vector <ll> dp(k+1, inf); dp[0]=0;
    vector <vector <pll>> H(k+1);
    for (ll i=0; i<n; i++)
    {
        s[i]=lower_bound(num.begin(), num.end(), s[i])-num.begin()+1;
        e[i]=lower_bound(num.begin(), num.end(), e[i])-num.begin()+1;
        H[e[i]].pb({s[i], w[i]});
    }
    BIT A(k+1), B(k+1);
    for (ll i=1; i<=k; i++)
    {
        for (auto [l, w]:H[i])
            A.update(0, l-1, 1), B.update(l, i-1, w);
        for (ll j=0; j<=i; j++)
        {
            if (A.query(j)>K) continue;
            dp[i]=min(dp[i], dp[j]+B.query(j));
        }
    }
    return dp[k];
}