Overview

This problem asks us to select team members from given employees and maximize the minimum of the total programming ability and the total design ability. At first glance, it seems like we need to carefully select which employees to include, but in fact, “selecting everyone” is always the optimal solution.

Analysis

Each employee’s ability values \(A_i, B_i\) are all positive integers greater than or equal to \(1\). When the set of selected employees is \(S\), the overall strength is defined as \(\min\left(\sum_{i \in S} A_i, \sum_{i \in S} B_i\right)\).

Now, consider adding an employee \(j\) who has not yet been selected to a group \(S\). Let \(S' = S \cup \{j\}\) be the group after adding employee \(j\). The total programming ability and total design ability change as follows: - Total programming ability: \(\sum_{i \in S'} A_i = \left(\sum_{i \in S} A_i\right) + A_j\) - Total design ability: \(\sum_{i \in S'} B_i = \left(\sum_{i \in S} B_i\right) + B_j\)

Since \(A_j \ge 1\) and \(B_j \ge 1\), adding an employee always increases both the total programming ability and the total design ability. Since both totals increase, their minimum \(\min\left(\sum A_i, \sum B_i\right)\) also always increases.

Concrete Example

Suppose a group \(S\) has ability totals of (programming, design) = \((10, 15)\). The overall strength is \(\min(10, 15) = 10\). If we add an employee with abilities \((A_j, B_j) = (3, 2)\), the new totals become \((13, 17)\), and the overall strength becomes \(\min(13, 17) = 13\), which is greater than before the addition.

In this way, the more members we add, the higher the overall strength becomes. Therefore, to maximize the overall strength, the optimal strategy is to select everyone for the team.

Algorithm

1. Compute the total programming ability of all given employees: \(sum\_A = \sum_{i=1}^N A_i\).
2. Similarly, compute the total design ability of all employees: \(sum\_B = \sum_{i=1}^N B_i\).
3. Output \(\min(sum\_A, sum\_B)\).

Complexity

• Time complexity: \(O(N)\) Since we scan all ability values once to compute the totals, the time complexity is proportional to the number of employees \(N\). This runs sufficiently fast for the constraint \(N \le 2 \times 10^5\).
• Space complexity: \(O(N)\) In the provided code, the input is read all at once and stored in a list, so the space complexity is \(O(N)\).

Implementation Notes

• Since the input can be as large as \(2 \times 10^5\) lines, in Python we can use sys.stdin.read().split() to read all input at once, enabling fast input processing.

• The answer can potentially be a very large number, but since Python natively supports arbitrary-precision integers, there is no concern about overflow. When implementing in other languages such as C++, care must be taken to ensure that the total fits within a 64-bit integer type (such as long long).

  Source Code

import sys

def main():
    # 入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    
    sum_A = 0
    sum_B = 0
    
    # 各社員の能力値を合計する
    for i in range(N):
        sum_A += int(input_data[2 * i + 1])
        sum_B += int(input_data[2 * i + 2])
        
    # 全員を選んだときが常に総合力が最大となる
    print(min(sum_A, sum_B))

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.5-flash-thinking.