Tehtävänanto

JOI-lukion Aoi päätti jakaa herkkuja ystävilleen.

Aoilla on $N$ ystävää, jotka on numeroitu luvusta $1$ lukuun $N$.

Aoilla on $X$ jäätelöä ja $Y$ suklaata. Aoi päätti jakaa kaikille $N$ ystävälleen kullekin $1$ herkun – joko jäätelön tai suklaan. Tässä taataan, että jäätelöitä ja suklaita on yhteensä vähintään $N$ kappaletta. Näin ollen Aoi pystyy jakamaan herkun kaikille ystävilleen.

Ystävä $i$ ($1 \le i \le N$) saa iloa $A_i$, jos hän saa jäätelön, ja iloa $B_i$, jos hän saa suklaan.

Tulosta suurin mahdollinen Aoin kaikkien ystävien saaman ilon yhteismäärä.

Rajoitukset

• $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$).
• Kaikki syötteen arvot ovat kokonaislukuja.

Osatehtävät

1. ($5$ pistettä) $N = 1$.
2. ($5$ pistettä) $X = N$, $Y = 0$.
3. ($5$ pistettä) $X = N$, $Y = N$.
4. ($25$ pistettä) $X = N$, $Y = 1$.
5. ($25$ pistettä) $X + Y = N$.
6. ($10$ pistettä) $N \le 10$.
7. ($25$ pistettä) Ei lisärajoituksia.

Syöte

Syöte annetaan seuraavassa muodossa:

N X Y
A_1 A_2 … A_N
B_1 B_2 … B_N

Tuloste

Tulosta suurin mahdollinen Aoin kaikkien ystävien saaman ilon yhteismäärä.

Älä tulosta mitään muuta kuin vastaus. (Älä esimerkiksi tulosta syötettä pyytävää tekstiä.)

Vastausmuodon osalta voit katsoa mallia harjoitustehtävistä ja niiden malliratkaisuista.

Esimerkki 1

Syöte

2 1 1
10 20
40 30

Tuloste

60

Aoilla on seuraavat $2$ tapaa jakaa herkut:

• Jos hän antaa ystävälle $1$ jäätelön ja ystävälle $2$ suklaan, ilon yhteismäärä on $A_1 + B_2 = 10 + 30 = 40$.
• Jos hän antaa ystävälle $1$ suklaan ja ystävälle $2$ jäätelön, ilon yhteismäärä on $B_1 + A_2 = 40 + 20 = 60$.

Näistä $2$ tavasta ilon yhteismäärä on suurin jälkimmäisessä tapauksessa, jolloin ilon yhteismäärä on $60$. Siispä tulostetaan $60$.

Tämä syöteesimerkki täyttää osatehtävien $5, 6, 7$ rajoitukset.

Esimerkki 2

Syöte

2 2 2
10 20
40 30

Tuloste

70

Aoilla on seuraavat $4$ tapaa jakaa herkut:

• Jos hän antaa sekä ystävälle $1$ että ystävälle $2$ jäätelön, ilon yhteismäärä on $A_1 + A_2 = 10 + 20 = 30$.
• Jos hän antaa ystävälle $1$ jäätelön ja ystävälle $2$ suklaan, ilon yhteismäärä on $A_1 + B_2 = 10 + 30 = 40$.
• Jos hän antaa ystävälle $1$ suklaan ja ystävälle $2$ jäätelön, ilon yhteismäärä on $B_1 + A_2 = 40 + 20 = 60$.
• Jos hän antaa sekä ystävälle $1$ että ystävälle $2$ suklaan, ilon yhteismäärä on $B_1 + B_2 = 40 + 30 = 70$.

Näistä $4$ tavasta ilon yhteismäärä on suurin viimeisessä tapauksessa, jolloin ilon yhteismäärä on $70$. Siispä tulostetaan $70$.

Tämä syöteesimerkki täyttää osatehtävien $3, 6, 7$ rajoitukset.

Esimerkki 3

Syöte

1 1 0
1234
5678

Tuloste

1234

Tässä syöteesimerkissä Aoilla on vain $1$ ystävä.

Tämä syöteesimerkki täyttää osatehtävien $1, 2, 5, 6, 7$ rajoitukset.

Esimerkki 4

Syöte

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

Tuloste

5867599604

Huomaa, että tuloste ei välttämättä mahdu 32-bittiseen kokonaislukutyyppiin.

Tämä syöteesimerkki täyttää osatehtävien $4, 6, 7$ rajoitukset.