Problembeskrivning

Aoi på JOI-gymnasiet har bestämt sig för att dela ut godsaker till sina vänner.

Aoi har $N$ vänner, som är numrerade från $1$ till $N$.

Aoi har $X$ glassar och $Y$ chokladbitar. Aoi har bestämt sig för att dela ut $1$ godsak – antingen en glass eller en chokladbit – till var och en av sina $N$ vänner. Det garanteras att det totala antalet glassar och chokladbitar är minst $N$. Därför kan Aoi dela ut godsaker till alla sina vänner.

Vän $i$ ($1 \le i \le N$) får glädjen $A_i$ om hen får en glass, och glädjen $B_i$ om hen får en chokladbit.

Skriv ut det största möjliga värdet för den sammanlagda glädjen som alla Aois vänner får.

Begränsningar

• $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$).
• Alla indatavärden är heltal.

Deluppgifter

1. ($5$ poäng) $N = 1$.
2. ($5$ poäng) $X = N$, $Y = 0$.
3. ($5$ poäng) $X = N$, $Y = N$.
4. ($25$ poäng) $X = N$, $Y = 1$.
5. ($25$ poäng) $X + Y = N$.
6. ($10$ poäng) $N \le 10$.
7. ($25$ poäng) Inga ytterligare begränsningar.

Indata

Indata ges i följande format:

N X Y
A_1 A_2 … A_N
B_1 B_2 … B_N

Utdata

Skriv ut det största möjliga värdet för den sammanlagda glädjen som alla Aois vänner får.

Skriv inte ut någonting annat än svaret. (Skriv till exempel inte ut någon text som uppmanar till inmatning.)

För svarsformatet kan du hänvisa till övningsuppgifterna och deras exempellösningar.

Exempel 1

Indata

2 1 1
10 20
40 30

Utdata

60

Det finns följande $2$ sätt för Aoi att dela ut godsakerna:

• Om hon ger en glass till vän $1$ och en chokladbit till vän $2$ blir den sammanlagda glädjen $A_1 + B_2 = 10 + 30 = 40$.
• Om hon ger en chokladbit till vän $1$ och en glass till vän $2$ blir den sammanlagda glädjen $B_1 + A_2 = 40 + 20 = 60$.

Av dessa $2$ sätt blir den sammanlagda glädjen som störst i det senare fallet, då den är $60$. Därför skrivs $60$ ut.

Detta indataexempel uppfyller begränsningarna för deluppgift $5, 6, 7$.

Exempel 2

Indata

2 2 2
10 20
40 30

Utdata

70

Det finns följande $4$ sätt för Aoi att dela ut godsakerna:

• Om hon ger glass till både vän $1$ och vän $2$ blir den sammanlagda glädjen $A_1 + A_2 = 10 + 20 = 30$.
• Om hon ger en glass till vän $1$ och en chokladbit till vän $2$ blir den sammanlagda glädjen $A_1 + B_2 = 10 + 30 = 40$.
• Om hon ger en chokladbit till vän $1$ och en glass till vän $2$ blir den sammanlagda glädjen $B_1 + A_2 = 40 + 20 = 60$.
• Om hon ger choklad till både vän $1$ och vän $2$ blir den sammanlagda glädjen $B_1 + B_2 = 40 + 30 = 70$.

Av dessa $4$ sätt blir den sammanlagda glädjen som störst i det sista fallet, då den är $70$. Därför skrivs $70$ ut.

Detta indataexempel uppfyller begränsningarna för deluppgift $3, 6, 7$.

Exempel 3

Indata

1 1 0
1234
5678

Utdata

1234

I detta indataexempel har Aoi bara $1$ vän.

Detta indataexempel uppfyller begränsningarna för deluppgift $1, 2, 5, 6, 7$.

Exempel 4

Indata

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

Observera att svaret kanske inte får plats i en 32-bitars heltalsdatatyp.

Detta indataexempel uppfyller begränsningarna för deluppgift $4, 6, 7$.