Untitled

class Solution {
public:
    using ll = long long;
    long long minCost(vector<int>& nums, vector<int>& cost) {
        int n = nums.size();
        ll largest = -1;
        vector<pair<ll, ll>> pairs(n);
        
        for (int i=0; i<n; ++i){
            pairs[i] = {nums[i], cost[i]};
            largest = max(largest, (ll) nums[i]);
        }

        sort(pairs.begin(), pairs.end());

        vector<ll> prefix(n+1), suffix(n+1);
        prefix[0] = 0; suffix[n] = 0;
        ll initial = pairs[0].first;
        ll initial_cost = 0;

        for (int i=0; i<n; ++i){
            prefix[i+1] = prefix[i] + pairs[i].second;
            suffix[n-i-1] = suffix[n-i] + pairs[n-i-1].second;
            initial_cost += (pairs[i].first - initial) * pairs[i].second;
        }

        vector<ll> costs(largest+1, LLONG_MAX);
        costs[initial] = initial_cost;

        int idx = 0;
        for (int i=initial+1; i<=largest; ++i){
            if (i > pairs[idx].first) idx += 1;
            costs[i] = costs[i-1] + prefix[idx] - suffix[idx];
        }

        ll ans = *min_element(costs.begin(), costs.end());
        return ans;        
    }
};