Overview

This problem asks you to consider all \(N\) fruits currently in the store and \(M\) newly delivered fruits together, select \(K\) fruits in descending order of sweetness, and find their total.

In other words, you need to find the “sum of the top \(K\) largest values” among \(N+M\) numbers.

Analysis

The key insight in this problem is that it doesn’t matter whether a fruit was originally in the store or newly delivered.
All that matters is selecting \(K\) fruits with the highest sweetness from the combined \(N+M\) fruits.

For example, if:

• \(A = [5, 1, 8]\)
• \(B = [4, 10]\)
• \(K = 3\)

then combining everything gives:

\([5, 1, 8, 4, 10]\)

Sorting in descending order gives:

\([10, 8, 5, 4, 1]\)

So the sum of the top \(3\) is:

\(10 + 8 + 5 = 23\)

Naive Approach

Exhaustively searching over all possible choices of \(K\) items results in an extremely large number of combinations, making it impractical.
Also, while repeatedly finding the maximum value \(K\) times is implementable, there is a much simpler approach.

How to Solve It

Put the sweetness of all fruits into a single array and sort it in descending order.
Then, the first \(K\) elements are exactly the \(K\) fruits selected in order of highest sweetness.

Since the constraint is \(N+M \leq 150000\), sorting in \(O((N+M)\log(N+M))\) is well within the time limit.

Algorithm

1. Read \(N, M, K\)
2. Read all \(N+M\) sweetness values into a single array vals
3. Sort vals in descending order
4. Output the sum of the first \(K\) elements

In the code, \(A_i\) and \(B_j\) are not distinguished and are simply read together as \(N+M\) values.
Since this problem ultimately just requires combining everything and comparing, this is sufficient.

Complexity

• Time complexity: \(O((N+M)\log(N+M))\)
• Space complexity: \(O(N+M)\)

Implementation Notes

• Since \(A_i\) and \(B_j\) are ultimately treated the same way, there is no need to store them in separate arrays.

• In Python, you can easily sort in descending order with vals.sort(reverse=True).

• The total sum can become large, but Python’s integer type handles it without any issues.

  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.4-high.