3961. Maximize Sum of Device Ratings

You are given a 2D integer array units of size m × n where units[i][j] represents the capacity of the j^th unit in the i^th device. Each device contains exactly n units.

The rating of a device is the minimum capacity among all its units.

You may perform the following operation any number of times (including zero):

• Choose a device i that has not been used as a source before.
• Remove exactly one unit from device i and add it to any different device.
• Then mark device i as used, so it cannot be chosen again as a source.

Return the maximum possible sum of the ratings of all devices after any number of such operations.

Note:

• Devices can receive units from multiple devices, regardless of whether they have been selected.
• The rating of an empty device is 0.

class Solution {
public:
    long long maxRatings(vector<vector<int>>& units) {
        int n = units.size(), m = units[0].size();
        if(m == 1) {
            long long res = 0;
            for(auto& u : units) res += u[0];
            return res;
        }
        vector<pair<long long, long long>> S;
        for(auto& u : units) {
            sort(begin(u), end(u));
            S.push_back({u[1],u[0]});
        }
        sort(rbegin(S), rend(S));
        vector<long long> picks{{S.back().first, S.back().second}};
        S.pop_back();
        long long res = 0;
        for(auto& [a,b] : S) {
            picks.push_back(b);
            res += a;
        }
        res += *min_element(begin(picks), end(picks));
        return res;
    }
};