Énoncé du problème

Aoi, élève au lycée JOI, a décidé de distribuer des friandises à ses amis.

Aoi a $N$ amis, numérotés de $1$ à $N$.

Aoi possède $X$ glaces et $Y$ chocolats. Elle a décidé de distribuer $1$ friandise — soit une glace, soit un chocolat — à chacun de ses $N$ amis. Il est garanti que le nombre total de glaces et de chocolats est supérieur ou égal à $N$. Par conséquent, Aoi peut distribuer des friandises à tous ses amis.

L'ami $i$ ($1 \le i \le N$) obtient une joie de $A_i$ s'il reçoit une glace, et une joie de $B_i$ s'il reçoit un chocolat.

Affichez la valeur maximale possible de la somme des joies obtenues par tous les amis d'Aoi.

Contraintes

• $1 \le N \le 200\,000$.
• $0 \le X \le N$.
• $0 \le Y \le N$.
• $N \le X + Y$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• $1 \le B_i \le 10^9$ ($1 \le i \le N$).
• Toutes les valeurs d'entrée sont des entiers.

Sous-tâches

1. ($5$ points) $N = 1$.
2. ($5$ points) $X = N$, $Y = 0$.
3. ($5$ points) $X = N$, $Y = N$.
4. ($25$ points) $X = N$, $Y = 1$.
5. ($25$ points) $X + Y = N$.
6. ($10$ points) $N \le 10$.
7. ($25$ points) Aucune contrainte supplémentaire.

Entrée

L'entrée est donnée sous le format suivant :

N X Y
A_1 A_2 … A_N
B_1 B_2 … B_N

Sortie

Affichez la valeur maximale possible de la somme des joies obtenues par tous les amis d'Aoi.

N'affichez rien d'autre que la réponse. (N'affichez pas non plus de texte demandant une saisie.)

Pour le format de réponse, vous pouvez consulter les problèmes d'entraînement et leurs exemples de solutions.

Exemple 1

Entrée

2 1 1
10 20
40 30

Sortie

60

Aoi a les $2$ façons suivantes de distribuer les friandises :

• Si elle donne une glace à l'ami $1$ et un chocolat à l'ami $2$, la joie totale est $A_1 + B_2 = 10 + 30 = 40$.
• Si elle donne un chocolat à l'ami $1$ et une glace à l'ami $2$, la joie totale est $B_1 + A_2 = 40 + 20 = 60$.

Parmi ces $2$ façons, la joie totale est maximale dans le second cas, où elle vaut $60$. On affiche donc $60$.

Cet exemple d'entrée vérifie les contraintes des sous-tâches $5, 6, 7$.

Exemple 2

Entrée

2 2 2
10 20
40 30

Sortie

70

Aoi a les $4$ façons suivantes de distribuer les friandises :

• Si elle donne une glace à la fois à l'ami $1$ et à l'ami $2$, la joie totale est $A_1 + A_2 = 10 + 20 = 30$.
• Si elle donne une glace à l'ami $1$ et un chocolat à l'ami $2$, la joie totale est $A_1 + B_2 = 10 + 30 = 40$.
• Si elle donne un chocolat à l'ami $1$ et une glace à l'ami $2$, la joie totale est $B_1 + A_2 = 40 + 20 = 60$.
• Si elle donne un chocolat à la fois à l'ami $1$ et à l'ami $2$, la joie totale est $B_1 + B_2 = 40 + 30 = 70$.

Parmi ces $4$ façons, la joie totale est maximale dans le dernier cas, où elle vaut $70$. On affiche donc $70$.

Cet exemple d'entrée vérifie les contraintes des sous-tâches $3, 6, 7$.

Exemple 3

Entrée

1 1 0
1234
5678

Sortie

1234

Dans cet exemple d'entrée, Aoi n'a qu'$1$ seul ami.

Cet exemple d'entrée vérifie les contraintes des sous-tâches $1, 2, 5, 6, 7$.

Exemple 4

Entrée

10 10 1
314159265 358979323 846264338 327950288 419716939 937510582 97494459 230781640 628620899 862803482
534211706 798214808 651328230 664709384 460955058 223172535 940812848 111745028 410270193 852110555

Sortie

5867599604

Notez que la sortie peut ne pas tenir dans un type entier 32 bits.

Cet exemple d'entrée vérifie les contraintes des sous-tâches $4, 6, 7$.