CCEX Suceava 2023 - clasa a V-a | Perechi

Enunţ

La ora de matematică, toți elevii se joacă următorul joc. Se dau doua șiruri de $N$, respectiv $M$ numere naturale nenule. La o operație, se alege câte un element din primul, respectiv al doilea șir, se elimină, iar la scor se adună suma lor ridicată la pătrat. Jocul se termină când unul dintre șiruri rămâne fără elemente. Ștefana vrea să maximizeze scorul pentru a lua un $10$ așa că vă roagă pe voi să o ajutați.

Cerinţă

Dându-se $N$, $M$ și cele două șiruri, să se calculeze scorul maxim pe care Ștefana îl poate obține, precum și operațiile pe care aceasta trebuie să le facă pentru a ajunge la rezultat.

Date de intrare

Fișierul de intrare perechi.in conține pe prima linie două numere naturale $N$ și $M$ cu semnificația din enunț. Pe a doua linie $N$ numere naturale, iar pe a treia $M$ numere naturale.

Date de ieşire

Fișierul de ieșire perechi.out conține pe prima linie scorul maxim.

Restricţii și precizări

• $1 \leq x \leq 10^7$ (x reprezintă elementele din cele două șiruri)
• $1 \leq N, M \leq 5000$
• Numerele din cele două șiruri sunt distincte două câte două
• Inițial scorul este $0$
• Pentru teste in valoare de $30$ de puncte, $N = 1$

Exemple

perechi.in

3 5
3 7 5
1 10 4 6 8

perechi.out

539

Explicații

În urma primei operații, scorul devine $289$. În urma celei de-a doua operații, scorul devine $458$. În urma celei de-a treia operații, scorul devine $539$. Se poate demonstra că acesta este maxim.