<p>You have <code>n</code> jobs and <code>m</code> workers. You are given three arrays: <code>difficulty</code>, <code>profit</code>, and <code>worker</code> where:</p>

<ul>
	<li><code>difficulty[i]</code> and <code>profit[i]</code> are the difficulty and the profit of the <code>i<sup>th</sup></code> job, and</li>
	<li><code>worker[j]</code> is the ability of <code>j<sup>th</sup></code> worker (i.e., the <code>j<sup>th</sup></code> worker can only complete a job with difficulty at most <code>worker[j]</code>).</li>
</ul>

<p>Every worker can be assigned <strong>at most one job</strong>, but one job can be <strong>completed multiple times</strong>.</p>

<ul>
	<li>For example, if three workers attempt the same job that pays <code>$1</code>, then the total profit will be <code>$3</code>. If a worker cannot complete any job, their profit is <code>$0</code>.</li>
</ul>

<p>Return the maximum profit we can achieve after assigning the workers to the jobs.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
<strong>Output:</strong> 100
<strong>Explanation:</strong> Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == difficulty.length</code></li>
	<li><code>n == profit.length</code></li>
	<li><code>m == worker.length</code></li>
	<li><code>1 &lt;= n, m &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= difficulty[i], profit[i], worker[i] &lt;= 10<sup>5</sup></code></li>
</ul>

static const bool Booster = [](){
    std::ios_base::sync_with_stdio(false);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
    return true;
}();

std::array<std::pair<int,int>, 10'000> profit_difficulty;
std::array<int, 10'000> worker;
size_t N;
size_t M;

void parse_string_profit_difficulty(const std::string& s, const bool is_first) {
    N = 0;
    int number = 0;
    for (size_t i = 1; i < s.size(); ++i) {
        if (s[i] == ',' || s[i] == ']') {
            if (is_first) {
                profit_difficulty[N].first = number;
            } else {
                profit_difficulty[N].second = number;
            }
            N++;
            number = 0;
        } else {
            number = number * 10 + (s[i] - '0');
        }
    }
}

void parse_string_worker(const std::string& s) {
    M = 0;
    int number = 0;
    for (size_t i = 1; i < s.size(); ++i) {
        if (s[i] == ',' || s[i] == ']') {
            worker[M] = number;
            M++;
            number = 0;
        } else {
            number = number * 10 + (s[i] - '0');
        }
    }
}

int maxProfitAssignment() {
    std::sort(std::begin(profit_difficulty), std::begin(profit_difficulty) + N, 
        [](const std::pair<int,int>& p1, const std::pair<int,int>& p2){
            if (p1.first == p2.first) {
                return p1.second < p2.second;
            }
            return p1.first > p2.first;
        }
    );
    std::sort(std::begin(worker), std::begin(worker) + M, std::greater<int>());
    int max_profit = 0;
    size_t i = 0;
    for (int j = 0; j < M; ++j) {
        while (i < N && worker[j] < profit_difficulty[i].second) { ++i; }
        if (i < N) {
            max_profit += profit_difficulty[i].first;
        }
    }
    return max_profit;
}

static bool Solve = [](){
    std::ofstream out("user.out");
    std::string s1, s2, s3;
    while (std::getline(std::cin, s1) && std::getline(std::cin, s2) && std::getline(std::cin, s3)) {
        parse_string_profit_difficulty(s1, false);  // difficulty
        parse_string_profit_difficulty(s2, true);   // profit
        parse_string_worker(s3);                    // worker
        out << maxProfitAssignment() << "\n";
    }
    out.flush();
    exit(0);
    return true;
}();

class Solution {
public:
    int maxProfitAssignment(std::vector<int>& difficulty, std::vector<int>& profit, std::vector<int>& worker) {
        const size_t N = profit.size();
        std::vector<std::pair<int,int>> prof(N);
        for (size_t i = 0; i < N; ++i) {
            prof[i] = {profit[i], difficulty[i]};
        }
        std::sort(std::begin(prof), std::end(prof), 
            [](const std::pair<int,int>& p1, const std::pair<int,int>& p2){
                if (p1.first == p2.first) {
                    return p1.second < p2.second;
                }
                return p1.first > p2.first;
            }
        );
        std::sort(std::begin(worker), std::end(worker), std::greater<int>());
        int max_profit = 0;
        size_t i = 0;
        for (int w : worker) {
            while (i < N && w < prof[i].second) { ++i; }
            if (i < N) {
                max_profit += prof[i].first;
            }
        }
        return max_profit;
    }
};
9184