1063 - Arme

Cerința

Vasile joacă (din nou!) jocul său preferat cu împuşcături. Personajul său are la brâu N arme, aşezate în N huse speciale, numerotate de la 1 la N. Arma din husa i are puterea pbi (1≤i≤N).

În camera armelor a găsit M arme, aşezate pe perete, în M locaţii, numerotate de la 1 la M. Pentru fiecare armă j (1≤j≤M) este cunoscută puterea sa pcj.

Vasile poate înlocui arme pe care le are la brâu cu arme aflate pe perete în camera armelor. La o înlocuire el ia arma de pe perete din locaţia j (1≤j≤M) şi o pune la brâu în husa i (1≤i≤N), iar arma din husa i o pune pe perete în locaţia j. Scrieţi un program care să determine suma maximă a puterilor armelor pe care le va avea la brâu Vasile după efectuarea înlocuirilor.

Date de intrare

Fișierul de intrare arme.in conține pe prima linie numerele naturale N M, reprezentând numărul de arme pe care le are la brâu, respectiv numărul de arme aflate în camera armelor. Pe a doua linie se află N numere naturale pb1 pb2 … pbN reprezentând în ordine puterile armelor pe care Vasile le are la brâu. Pe a treia linie se află M numere naturale pc1 pc2 … pcM reprezentând în ordine puterile armelor aflate în camera armelor. Numerele scrise pe aceeaşi linie sunt separate prin spaţiu.

Date de ieșire

Fișierul de ieșire arme.out va conține o singură linie pe care va fi scrisă suma maximă a puterilor armelor de la brâul lui Vasile, după efectuarea înlocuirilor.

Restricții și precizări

• 1 ≤ N, M ≤ 1000
• Puterile armelor sunt numere naturale ≤ 10.000.
• Greutatea și valoarea fiecărei arme sunt numere întregi pozitive

Exemplu 1

Intrare

3 2
3 1 7
4 5

Iesire

16

Rezolvare

def main():
    with open("arme.in", "r") as f:
        # Citim dimensiunile N și M
        N, M = map(int, f.readline().strip().split())
        
        # Citim puterile armelor de la brâu
        puteri_brau = list(map(int, f.readline().strip().split()))
        
        # Citim puterile armelor din camera armelor
        puteri_camera = list(map(int, f.readline().strip().split()))

    # Restricții și precizări
    assert 1 <= N <= 1000, "N trebuie să fie între 1 și 1000"
    assert 1 <= M <= 1000, "M trebuie să fie între 1 și 1000"
    assert all(1 <= pb <= 10000 for pb in puteri_brau), "Puterea armelor de la brâu trebuie să fie între 1 și 10000"
    assert all(1 <= pc <= 10000 for pc in puteri_camera), "Puterea armelor din cameră trebuie să fie între 1 și 10000"

    # Sortăm puterile armelor de la brâu în ordine crescătoare
    puteri_brau.sort()

    # Sortăm puterile armelor din cameră în ordine descrescătoare
    puteri_camera.sort(reverse=True)

    # Înlocuim armele de la brâu cu cele din cameră
    for i in range(min(N, M)):
        if puteri_camera[i] > puteri_brau[i]:
            puteri_brau[i] = puteri_camera[i]
        else:
            break

    # Calculăm suma maximă a puterilor armelor de la brâu
    suma_maxima = sum(puteri_brau)

    with open("arme.out", "w") as f:
        f.write(f"{suma_maxima}\n")

if __name__ == "__main__":
    main()