Overview

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

Analysis

For a chosen set of employees \(S\), the team’s overall strength is

\(\min(\sum_{i \in S} A_i, \sum_{i \in S} B_i)\)

The key observation here is that, due to the constraints, all \(A_i, B_i\) are positive integers.

In other words, when adding an employee to the team:

• The total programming ability always increases
• The total design ability also always increases

For example, suppose the current totals are:

• Total programming ability: \(X\)
• Total design ability: \(Y\)

When adding employee \(i\):

• Total programming ability becomes: \(X + A_i\)
• Total design ability becomes: \(Y + B_i\)

Since \(A_i > 0, B_i > 0\), both totals increase.
Therefore,

\(\min(X + A_i, Y + B_i) \geq \min(X, Y)\)

holds.

This means that adding an employee never decreases the overall strength.

Therefore, to maximize the overall strength, we should select all available employees.

A naive approach of trying all subsets would have \(2\) choices (select or not) per employee, resulting in \(2^N\) total combinations.
Since \(N \leq 2 \times 10^5\), this is far too slow.

However, due to the property above, there is no need to search through subsets — it suffices to simply compute the value when everyone is selected.

Algorithm

When all employees are on the team:

• The total programming ability is \(\sum_{i=1}^{N} A_i\)
• The total design ability is \(\sum_{i=1}^{N} B_i\)

The answer is the smaller of the two, so we output:

\(\min(\sum_{i=1}^{N} A_i, \sum_{i=1}^{N} B_i)\)

The steps are as follows:

1. Read the input
2. Compute the sum of all \(A_i\)
3. Compute the sum of all \(B_i\)
4. Output the smaller of the two

Complexity

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

Implementation Details

The input is in the following format:

N
A_1 B_1
A_2 B_2
...
A_N B_N

In the code, the entire input is read as a list of integers data.

data = list(map(int, sys.stdin.buffer.read().split()))

At this point, data is arranged as follows:

[N, A_1, B_1, A_2, B_2, ..., A_N, B_N]

Therefore,

data[1::2]

extracts \(A_1, A_2, ..., A_N\).

And,

data[2::2]

extracts \(B_1, B_2, ..., B_N\).

We compute the sum of each and output the smaller value.

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    sum_a = sum(data[1::2])
    sum_b = sum(data[2::2])
    print(min(sum_a, sum_b))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.