Overview

This is a problem where you combine the sweetness of all fruits (the existing \(N\) plus the new \(M\)) and find the sum of the first \(K\) elements when sorted in descending order. In other words, you can solve it by directly implementing the operation of “selecting the top \(K\) elements.”

Analysis

The key observation is the following single point:

• Whether a fruit is an original one or a newly arrived one doesn’t matter — the selection criterion is based solely on “the magnitude of sweetness.”

Therefore, there is no need to handle arrays \(A\) and \(B\) separately. Putting everything into a single array, sorting in descending order, and summing the first \(K\) elements is the most straightforward approach.

Comparison with a Naive Approach

• For example, with a method like “find the maximum value one at a time and add it, repeating \(K\) times,” each search takes \(O(N+M)\), resulting in an overall complexity of \(O(K(N+M))\), which is inefficient.
• Since the constraint is \(N+M \le 150000\), sorting everything once in \(O((N+M)\log(N+M))\) is fast enough.

Concrete Example

For instance, if \(A = [5, 1, 4],\ B = [3, 10],\ K=3\), combining gives \([5,1,4,3,10]\), and in descending order \([10,5,4,3,1]\). The sum of the first 3 elements is \(10+5+4=19\).

Algorithm

1. Read \(N, M, K\).
2. Read the sweetness values from the following \(N+M\) lines into a single array vals.
3. Sort vals in descending order.
4. Output the sum of vals[:K].

The provided code implements this procedure directly.

Complexity

• Time complexity: \(O((N+M)\log(N+M))\) (dominated by sorting)
• Space complexity: \(O(N+M)\) (storing all elements in an array)

Implementation Notes

• Since the number of input lines is large, using sys.stdin.readline ensures stable and fast input.

• In Python, this can be written concisely with vals.sort(reverse=True) and sum(vals[:K]).

• The maximum possible sum is around \(K \times 10^9\), but Python’s integers do not overflow, so there is no concern.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    vals = [int(input()) for _ in range(N + M)]
    vals.sort(reverse=True)
    print(sum(vals[:K]))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.