Problembeskrivelse

Aoi ved JOI videregående skole har bestemt seg for å dele ut snacks til vennene sine.

Aoi har $N$ venner, som er nummerert fra $1$ til $N$.

Aoi har $X$ iskrem og $Y$ sjokolader. Aoi har bestemt seg for å dele ut $1$ snacks – enten en iskrem eller en sjokolade – til hver av de $N$ vennene sine. Her garanteres det at det til sammen er minst $N$ iskrem og sjokolader. Derfor er det mulig for Aoi å dele ut snacks til alle vennene sine.

Venn $i$ ($1 \le i \le N$) får gleden $A_i$ hvis hen får en iskrem, og gleden $B_i$ hvis hen får en sjokolade.

Skriv ut den største mulige verdien for den totale gleden som alle vennene til Aoi oppnår.

Begrensninger

• $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$).
• Alle inndataverdier er heltall.

Deloppgaver

1. ($5$ poeng) $N = 1$.
2. ($5$ poeng) $X = N$, $Y = 0$.
3. ($5$ poeng) $X = N$, $Y = N$.
4. ($25$ poeng) $X = N$, $Y = 1$.
5. ($25$ poeng) $X + Y = N$.
6. ($10$ poeng) $N \le 10$.
7. ($25$ poeng) Ingen ytterligere begrensninger.

Inndata

Inndataene gis i følgende format:

N X Y
A_1 A_2 … A_N
B_1 B_2 … B_N

Utdata

Skriv ut den største mulige verdien for den totale gleden som alle vennene til Aoi oppnår.

Ikke skriv ut noe annet enn svaret. (Ikke skriv ut tekst som ber om inndata eller lignende.)

For svarsformatet kan du se på øvingsoppgavene og eksempelløsningene deres.

Eksempel 1

Inndata

2 1 1
10 20
40 30

Utdata

60

Det finnes følgende $2$ måter for Aoi å dele ut snacks på:

• Hvis hun gir iskrem til venn $1$ og sjokolade til venn $2$, blir den totale gleden $A_1 + B_2 = 10 + 30 = 40$.
• Hvis hun gir sjokolade til venn $1$ og iskrem til venn $2$, blir den totale gleden $B_1 + A_2 = 40 + 20 = 60$.

Blant disse $2$ måtene blir den totale gleden størst i det siste tilfellet, der den totale gleden er $60$. Derfor skrives $60$ ut.

Dette inndataeksempelet oppfyller begrensningene i deloppgave $5, 6, 7$.

Eksempel 2

Inndata

2 2 2
10 20
40 30

Utdata

70

Det finnes følgende $4$ måter for Aoi å dele ut snacks på:

• Hvis hun gir iskrem til både venn $1$ og venn $2$, blir den totale gleden $A_1 + A_2 = 10 + 20 = 30$.
• Hvis hun gir iskrem til venn $1$ og sjokolade til venn $2$, blir den totale gleden $A_1 + B_2 = 10 + 30 = 40$.
• Hvis hun gir sjokolade til venn $1$ og iskrem til venn $2$, blir den totale gleden $B_1 + A_2 = 40 + 20 = 60$.
• Hvis hun gir sjokolade til både venn $1$ og venn $2$, blir den totale gleden $B_1 + B_2 = 40 + 30 = 70$.

Blant disse $4$ måtene blir den totale gleden størst i det siste tilfellet, der den totale gleden er $70$. Derfor skrives $70$ ut.

Dette inndataeksempelet oppfyller begrensningene i deloppgave $3, 6, 7$.

Eksempel 3

Inndata

1 1 0
1234
5678

Utdata

1234

I dette inndataeksempelet har Aoi bare $1$ venn.

Dette inndataeksempelet oppfyller begrensningene i deloppgave $1, 2, 5, 6, 7$.

Eksempel 4

Inndata

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

Utdata

5867599604

Merk at svaret kanskje ikke får plass i en 32-biters heltallstype.

Dette inndataeksempelet oppfyller begrensningene i deloppgave $4, 6, 7$.