Consider determining the box to give to people \(1, 2, \ldots, M\) in this order.

The following greedy strategy executed for each \(i = 1, 2, \ldots , M\) in order is valid.

• To person \(i\), give the undistributed box containing at least \(B_i\) candies with the smallest number of candies in it. (Let us call this strategy \((\bigstar)\).)

We will assume that this solution is not optimal to deduce a contradiction.

Take an optimal solution.

In this optimal solution, there is an \(i\) that violates the strategy \((\bigstar)\). Take the minimum such \(i\). Let box \(X\) be the box that you would give to person \(i\) if you obey the strategy \((\bigstar)\) up to \(1,2,\ldots, i-1, i\). (Precisely speaking, the box itself is not unique, but the number of snacks is.) In the taken optimal solution, if box \(X\) is not given to anyone, then giving person \(i\) box \(X\) improves the solution, which contradicts the optimality. Thus you will give it to a person \(j\). Consider swapping the boxes to give to person \(i\) and to person \(j\). This operation keeps optimality, but the minimum \(i\) that violates \((\bigstar)\) strictly increases, so repeating this yields a contradiction. Hence, the greedy algorithm has been justified.

Therefore, it is sufficient to simulate this greedy algorithm fast enough. This can be done by using a data structure like std::multiset in C++, or using the sliding window trick by using the fact that \(A\) and \(B\) can be sorted without changing the answer.

Sample code

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    rep(i, n) cin >> a[i];
    rep(i, m) cin >> b[i];
    multiset<int> st;
    rep(i, n) st.insert(a[i]);
    ll ans = 0;
    rep(i, m) {
        auto v = st.lower_bound(b[i]);
        if (v == st.end()) {
            cout << -1 << '\n';
            return 0;
        }
        ans += *v;
        st.erase(v);
    }
    cout << ans << '\n';
}