Overview

The problem asks us to select a subset \(S\) of employees and maximize \(\min(\sum_{i \in S} A_i, \sum_{i \in S} B_i)\).
Since all ability values are positive, the conclusion is that selecting everyone is optimal.

Analysis

For a chosen set of employees \(S\), the overall strength is defined as

\(\min(\text{sum of programming abilities}, \text{sum of design abilities})\)

The key observation here is that, due to the constraints, for all employees

\(A_i \geq 1,\ B_i \geq 1\)

This means that adding any employee will:

• Always increase the sum of programming abilities
• Always increase the sum of design abilities

For example, suppose the totals for some set \(S\) are:

• Sum of programming abilities: \(x\)
• Sum of design abilities: \(y\)

If we add employee \(i\), the totals become:

• Sum of programming abilities: \(x + A_i\)
• Sum of design abilities: \(y + B_i\)

Since both \(A_i\) and \(B_i\) are positive, both sums increase.
Therefore,

\(\min(x + A_i, y + B_i)\)

can never be smaller than the original

\(\min(x, y)\)

In other words, adding an employee never hurts.
Therefore, to obtain the maximum overall strength, we should select all available employees.

If we naively try all subsets, there are \(2^N - 1\) candidates.
Since \(N \leq 2 \times 10^5\), this is far too slow.

However, due to the observation above, there is no need to examine subsets — it suffices to consider only the case where everyone is selected.

Algorithm

When selecting everyone, let:

• \(\text{sumA}\) be the sum of programming abilities
• \(\text{sumB}\) be the sum of design abilities

The answer is

\(\min(\text{sumA}, \text{sumB})\)

The procedure is as follows:

1. Read \(N\)
2. For each employee, read \(A_i, B_i\)
3. Add \(A_i\) to \(\text{sumA}\)
4. Add \(B_i\) to \(\text{sumB}\)
5. Output \(\min(\text{sumA}, \text{sumB})\)

For example, consider the following input:

Employee	\(A_i\)	\(B_i\)
1	3	10
2	5	2
3	4	6

Selecting everyone gives:

\(\text{sumA} = 3 + 5 + 4 = 12\)

\(\text{sumB} = 10 + 2 + 6 = 18\)

So the overall strength is

\(\min(12, 18) = 12\)

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

The total values can be as large as

\(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\)

This does not fit in an int type, so in C++ you need to use long long.

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    long long sumA = 0, sumB = 0;
    for (int i = 0; i < N; i++) {
        long long A, B;
        cin >> A >> B;
        sumA += A;
        sumB += B;
    }

    cout << min(sumA, sumB) << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.