#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
map<int, int> m;
long long int z = 0, f[5005];
vector<pair<int, int>> g[5005], gg[5005];
long long int min_charge(int k, vector<int> s, vector<int> e, vector<int> w) {
    vector<int> v;
    for (int w : s) v.push_back(w);
    for (int w : e) v.push_back(w + 1);
    sort(v.begin(), v.end());
    for (int w : v) {
        if (!m.count(w)) {
            m[w] = ++z;
        }
    }
    int n = s.size();
    for (int i = 0; i < n; i++) {
        s[i] = m[s[i]];
        e[i] = m[e[i]] - 1;
        g[s[i]].push_back({e[i], w[i]});
        gg[e[i]].push_back({s[i], w[i]});
    }
    for (int i = 1; i <= z; i++) {
        priority_queue<long long int> q;
        f[i] = 1e18;
        long long int c = 0;
        for (int j = i; j >= 1; j--) {
            for (auto w : gg[j]) {
                c += w.second;
            }
            for (auto w : g[j]) {
                if (w.first <= i) {
                    c -= w.second;
                    q.push(-w.second);
                    while (q.size() > k) {
                        c -= q.top();
                        q.pop();
                    }
                }
            }
            f[i] = min(f[i], f[j - 1] + c);
        }
    }
    return f[z];
}