Koxia and Whiteboards (Codeforces 1770A)
Tags: Greedy, brute force

Kiyora has $$$n$$$ whiteboards numbered from $$$1$$$ to $$$n$$$. Initially, the $$$i$$$-th whiteboard has the integer $$$a_i$$$ written on it.Koxia performs $$$m$$$ operations. The $$$j$$$-th operation is to choose one of the whiteboards and change the integer written on it to $$$b_j$$$.Find the maximum possible sum of integers written on the whiteboards after performing all $$$m$$$ operations.

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 100$$$).The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).The third line of each test case contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i \le 10^9$$$).

Output: For each test case, output a single integer — the maximum possible sum of integers written on whiteboards after performing all $$$m$$$ operations.

Note: In the first test case, Koxia can perform the operations as follows:  Choose the $$$1$$$-st whiteboard and rewrite the integer written on it to $$$b_1=4$$$.  Choose the $$$2$$$-nd whiteboard and rewrite to $$$b_2=5$$$. After performing all operations, the numbers on the three whiteboards are $$$4$$$, $$$5$$$ and $$$3$$$ respectively, and their sum is $$$12$$$. It can be proven that this is the maximum possible sum achievable.In the second test case, Koxia can perform the operations as follows:  Choose the $$$2$$$-nd whiteboard and rewrite to $$$b_1=3$$$.  Choose the $$$1$$$-st whiteboard and rewrite to $$$b_2=4$$$.  Choose the $$$2$$$-nd whiteboard and rewrite to $$$b_3=5$$$. The sum is $$$4 + 5 = 9$$$. It can be proven that this is the maximum possible sum achievable.

Sample Inputs:
4
3 2
1 2 3
4 5
2 3
1 2
3 4 5
1 1
100
1
5 3
1 1 1 1 1
1000000000 1000000000 1000000000

Sample Outputs:
12
9
1
3000000002

Solution (Python):
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    x = list(map(int, input().split()))
    y = list(map(int, input().split()))
    z = x + y
    z[:n + m - 1] = sorted(z[:n + m - 1])
    z.reverse()
    print(sum(z[:n]))

Solution (Python):
from heapq import *

def solution():
    (n, m) = map(int, input().split())
    a = [int(i) for i in input().split()]
    heapify(a)
    b = [int(i) for i in input().split()]
    for i in b:
        heapreplace(a, i)
    print(sum(a))
t = int(input())
for _ in range(t):
    solution()

Solution (Python):
import heapq
import math

def I():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

def S():
    return input()
mod = 10 ** 9 + 7

def main(h, b):
    mini = h[0]
    for i in range(len(b)):
        heapq.heapreplace(h, b[i])
    summ = 0
    for i in h:
        summ += i
    return summ
t = I()
while t:
    (n, m) = MI()
    a = LI()
    b = LI()
    heapq.heapify(a)
    print(main(a, b))
    t -= 1