Overview

Given \(N\) existing fruits and \(M\) new fruits, for a total of \(N+M\) fruits, the problem asks to find the total sweetness when selecting \(K\) fruits in decreasing order of sweetness.

Analysis

The key point of this problem is that there is no need to distinguish “which fruits were originally there and which ones newly arrived”.

By treating all fruits as a single group and simply selecting the \(K\) sweetest ones (those with the largest values), we can obtain the desired total.

Efficient Selection

The most straightforward and reliable method to “select the top \(K\) in decreasing order” is to sort all fruits in descending order (from largest to smallest).

Checking the constraints, the total number of fruits \(N+M\) is at most \(150,000\). The time complexity of sorting algorithms in common programming languages is \(O(L \log L)\) (where \(L\) is the number of elements), and in this case the computation is approximately \(1.5 \times 10^5 \times \log(1.5 \times 10^5) \approx 2.5 \times 10^6\) operations. This is well within the typical competitive programming time limit (2 seconds).

Algorithm

The problem can be solved with the following steps:

1. Store the sweetness values of all fruits \(A_1, \dots, A_N\) and \(B_1, \dots, B_M\) into a single list (array).
2. Sort the list in descending order (from largest to smallest).
3. Take the first \(K\) elements from the sorted list and compute their sum.
4. Output the computed total.

Complexity

Let \(L = N + M\).

• Time complexity: \(O(L \log L)\)
  • Reading all elements takes \(O(L)\), sorting takes \(O(L \log L)\), and computing the sum of the first \(K\) elements takes \(O(K)\). Overall, the sorting complexity dominates.
• Space complexity: \(O(L)\)
  • A list is needed to store the \(N+M\) elements.

Implementation Notes

• Fast I/O: In Python, when the number of data items exceeds \(10^5\), instead of repeatedly calling input(), using sys.stdin.read().split() to read all input at once and then converting to numbers can significantly reduce execution time.

• Slicing and Summation: When selecting \(K\) elements from the sorted list, combining Python’s list slicing fruits[:k] with the sum() function allows computing the total concisely and efficiently.

  Source Code

import sys

def solve():
    # 全ての入力を一度に読み込み、空白（スペース、タブ、改行）で分割してトークン化します。
    # 150,000個程度のデータ量であれば、この方法がPythonにおいて非常に高速です。
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合、何もせず終了します。
    if not input_data:
        return
    
    # 入力の1行目には N, M, K が含まれています。
    # ここでは、上位 K 個を選ぶための K の値を取得します。
    # N = int(input_data[0])
    # M = int(input_data[1])
    k = int(input_data[2])
    
    # 4番目の要素（インデックス3）以降が全てのフルーツの甘さ Ai および Bj です。
    # これらを整数に変換してリストに格納します。
    fruits = list(map(int, input_data[3:]))
    
    # 甘さの大きい順に並べるため、リストを降順（大きい順）にソートします。
    # Pythonの sort() は非常に高速な Timsort アルゴリズムを使用しています。
    fruits.sort(reverse=True)
    
    # 先頭から K 個の要素（甘さの大きい順に K 個）を取り出し、その合計を計算します。
    # 制約により K <= N + M であることが保証されています。
    result = sum(fruits[:k])
    
    # 合計値を出力します。
    print(result)

if __name__ == '__main__':
    solve()

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