Verkefnalýsing

Aoi í framhaldsskólanum JOI ákvað að úthluta góðgæti til vina sinna.

Aoi á $N$ vini sem eru númeraðir frá $1$ til $N$.

Aoi á $X$ ísa og $Y$ súkkulaðistykki. Aoi ákvað að gefa öllum $N$ vinum sínum $1$ góðgæti hverjum — annaðhvort ís eða súkkulaði. Hér er tryggt að ísarnir og súkkulaðistykkin séu samtals að minnsta kosti $N$. Því getur Aoi gefið öllum vinum sínum góðgæti.

Vinur $i$ ($1 \le i \le N$) fær gleðina $A_i$ ef hann fær ís, en gleðina $B_i$ ef hann fær súkkulaði.

Prentaðu mesta mögulega gildið á samanlagðri gleði sem allir vinir Aoi fá.

Skorður

• $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$).
• Öll inntaksgildi eru heiltölur.

Undirverkefni

1. ($5$ stig) $N = 1$.
2. ($5$ stig) $X = N$, $Y = 0$.
3. ($5$ stig) $X = N$, $Y = N$.
4. ($25$ stig) $X = N$, $Y = 1$.
5. ($25$ stig) $X + Y = N$.
6. ($10$ stig) $N \le 10$.
7. ($25$ stig) Engar viðbótarskorður.

Inntak

Inntakið er gefið á eftirfarandi sniði:

N X Y
A_1 A_2 … A_N
B_1 B_2 … B_N

Úttak

Prentaðu mesta mögulega gildið á samanlagðri gleði sem allir vinir Aoi fá.

Ekki prenta neitt annað en svarið. (Til dæmis skal ekki prenta texta sem biður um inntak.)

Varðandi snið svarsins má styðjast við æfingadæmin og sýnilausnir þeirra.

Dæmi 1

Inntak

2 1 1
10 20
40 30

Úttak

60

Það eru eftirfarandi $2$ leiðir fyrir Aoi til að úthluta góðgætinu:

• Ef hún gefur vini $1$ ís og vini $2$ súkkulaði er samanlögð gleði $A_1 + B_2 = 10 + 30 = 40$.
• Ef hún gefur vini $1$ súkkulaði og vini $2$ ís er samanlögð gleði $B_1 + A_2 = 40 + 20 = 60$.

Af þessum $2$ leiðum er samanlögð gleði mest í síðara tilfellinu, og er þá $60$. Því er prentað $60$.

Þetta inntaksdæmi uppfyllir skorður undirverkefna $5, 6, 7$.

Dæmi 2

Inntak

2 2 2
10 20
40 30

Úttak

70

Það eru eftirfarandi $4$ leiðir fyrir Aoi til að úthluta góðgætinu:

• Ef hún gefur bæði vini $1$ og vini $2$ ís er samanlögð gleði $A_1 + A_2 = 10 + 20 = 30$.
• Ef hún gefur vini $1$ ís og vini $2$ súkkulaði er samanlögð gleði $A_1 + B_2 = 10 + 30 = 40$.
• Ef hún gefur vini $1$ súkkulaði og vini $2$ ís er samanlögð gleði $B_1 + A_2 = 40 + 20 = 60$.
• Ef hún gefur bæði vini $1$ og vini $2$ súkkulaði er samanlögð gleði $B_1 + B_2 = 40 + 30 = 70$.

Af þessum $4$ leiðum er samanlögð gleði mest í síðasta tilfellinu, og er þá $70$. Því er prentað $70$.

Þetta inntaksdæmi uppfyllir skorður undirverkefna $3, 6, 7$.

Dæmi 3

Inntak

1 1 0
1234
5678

Úttak

1234

Í þessu inntaksdæmi á Aoi aðeins $1$ vin.

Þetta inntaksdæmi uppfyllir skorður undirverkefna $1, 2, 5, 6, 7$.

Dæmi 4

Inntak

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

Úttak

5867599604

Athugið að úttakið rúmast hugsanlega ekki í 32-bita heiltölutagi.

Þetta inntaksdæmi uppfyllir skorður undirverkefna $4, 6, 7$.