Testo del problema

Aoi della scuola superiore JOI ha deciso di distribuire dei dolci ai suoi amici.

Aoi ha $N$ amici, numerati da $1$ a $N$.

Aoi possiede $X$ gelati e $Y$ cioccolatini. Ha deciso di distribuire $1$ dolce — un gelato oppure un cioccolatino — a ciascuno dei suoi $N$ amici. È garantito che il numero totale di gelati e cioccolatini è almeno $N$. Pertanto, Aoi può distribuire i dolci a tutti i suoi amici.

L'amico $i$ ($1 \le i \le N$) ottiene una felicità pari ad $A_i$ se riceve un gelato, e una felicità pari a $B_i$ se riceve un cioccolatino.

Stampa il valore massimo possibile della felicità totale ottenuta da tutti gli amici di Aoi.

Vincoli

• $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$).
• Tutti i valori in input sono numeri interi.

Sottoproblemi

1. ($5$ punti) $N = 1$.
2. ($5$ punti) $X = N$, $Y = 0$.
3. ($5$ punti) $X = N$, $Y = N$.
4. ($25$ punti) $X = N$, $Y = 1$.
5. ($25$ punti) $X + Y = N$.
6. ($10$ punti) $N \le 10$.
7. ($25$ punti) Nessun vincolo aggiuntivo.

Input

L'input è fornito nel seguente formato:

N X Y
A_1 A_2 … A_N
B_1 B_2 … B_N

Output

Stampa il valore massimo possibile della felicità totale ottenuta da tutti gli amici di Aoi.

Non stampare nient'altro oltre alla risposta. (Ad esempio, non stampare frasi che richiedono l'input.)

Per il formato di risposta, puoi fare riferimento ai problemi di prova e ai relativi esempi di soluzione.

Esempio 1

Input

2 1 1
10 20
40 30

Output

60

Ci sono i seguenti $2$ modi in cui Aoi può distribuire i dolci:

• Se dà un gelato all'amico $1$ e un cioccolatino all'amico $2$, la felicità totale è $A_1 + B_2 = 10 + 30 = 40$.
• Se dà un cioccolatino all'amico $1$ e un gelato all'amico $2$, la felicità totale è $B_1 + A_2 = 40 + 20 = 60$.

Tra questi $2$ modi, la felicità totale è massima nel secondo caso, in cui vale $60$. Pertanto, si stampa $60$.

Questo esempio di input soddisfa i vincoli dei sottoproblemi $5, 6, 7$.

Esempio 2

Input

2 2 2
10 20
40 30

Output

70

Ci sono i seguenti $4$ modi in cui Aoi può distribuire i dolci:

• Se dà il gelato sia all'amico $1$ che all'amico $2$, la felicità totale è $A_1 + A_2 = 10 + 20 = 30$.
• Se dà un gelato all'amico $1$ e un cioccolatino all'amico $2$, la felicità totale è $A_1 + B_2 = 10 + 30 = 40$.
• Se dà un cioccolatino all'amico $1$ e un gelato all'amico $2$, la felicità totale è $B_1 + A_2 = 40 + 20 = 60$.
• Se dà il cioccolatino sia all'amico $1$ che all'amico $2$, la felicità totale è $B_1 + B_2 = 40 + 30 = 70$.

Tra questi $4$ modi, la felicità totale è massima nell'ultimo caso, in cui vale $70$. Pertanto, si stampa $70$.

Questo esempio di input soddisfa i vincoli dei sottoproblemi $3, 6, 7$.

Esempio 3

Input

1 1 0
1234
5678

Output

1234

In questo esempio di input, Aoi ha solo $1$ amico.

Questo esempio di input soddisfa i vincoli dei sottoproblemi $1, 2, 5, 6, 7$.

Esempio 4

Input

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

Output

5867599604

Nota che il risultato potrebbe non entrare in un tipo intero a 32 bit.

Questo esempio di input soddisfa i vincoli dei sottoproblemi $4, 6, 7$.