Aufgabenstellung

Aoi von der JOI-Oberschule hat beschlossen, Süßigkeiten an ihre Freunde zu verteilen.

Aoi hat $N$ Freunde, die von $1$ bis $N$ nummeriert sind.

Aoi besitzt $X$ Eiscremes und $Y$ Schokoladen. Sie hat beschlossen, jedem ihrer $N$ Freunde jeweils $1$ Süßigkeit – entweder ein Eis oder eine Schokolade – zu geben. Dabei ist garantiert, dass die Gesamtzahl an Eiscremes und Schokoladen mindestens $N$ beträgt. Somit ist es Aoi möglich, an alle ihre Freunde Süßigkeiten zu verteilen.

Freund $i$ ($1 \le i \le N$) erhält eine Freude von $A_i$, wenn er ein Eis bekommt, und eine Freude von $B_i$, wenn er eine Schokolade bekommt.

Gib den größtmöglichen Wert für die Summe der Freude aus, die alle Freunde von Aoi zusammen erhalten können.

Bedingungen

• $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 Eingabewerte sind ganze Zahlen.

Teilaufgaben

1. ($5$ Punkte) $N = 1$.
2. ($5$ Punkte) $X = N$, $Y = 0$.
3. ($5$ Punkte) $X = N$, $Y = N$.
4. ($25$ Punkte) $X = N$, $Y = 1$.
5. ($25$ Punkte) $X + Y = N$.
6. ($10$ Punkte) $N \le 10$.
7. ($25$ Punkte) Keine weiteren Einschränkungen.

Eingabe

Die Eingabe erfolgt im folgenden Format:

N X Y
A_1 A_2 … A_N
B_1 B_2 … B_N

Ausgabe

Gib den größtmöglichen Wert für die Summe der Freude aus, die alle Freunde von Aoi zusammen erhalten können.

Gib nichts anderes als die Antwort aus. (Gib z. B. auch keinen Text zur Eingabeaufforderung aus.)

Für das Antwortformat kannst du dich an den Übungsaufgaben und ihren Beispiellösungen orientieren.

Beispiel 1

Eingabe

2 1 1
10 20
40 30

Ausgabe

60

Es gibt die folgenden $2$ Möglichkeiten für Aoi, die Süßigkeiten zu verteilen:

• Wenn sie Freund $1$ ein Eis und Freund $2$ eine Schokolade gibt, beträgt die Gesamtfreude $A_1 + B_2 = 10 + 30 = 40$.
• Wenn sie Freund $1$ eine Schokolade und Freund $2$ ein Eis gibt, beträgt die Gesamtfreude $B_1 + A_2 = 40 + 20 = 60$.

Unter diesen $2$ Möglichkeiten ist die Gesamtfreude im zweiten Fall am größten und beträgt dort $60$. Daher wird $60$ ausgegeben.

Dieses Eingabebeispiel erfüllt die Bedingungen der Teilaufgaben $5, 6, 7$.

Beispiel 2

Eingabe

2 2 2
10 20
40 30

Ausgabe

70

Es gibt die folgenden $4$ Möglichkeiten für Aoi, die Süßigkeiten zu verteilen:

• Wenn sie sowohl Freund $1$ als auch Freund $2$ ein Eis gibt, beträgt die Gesamtfreude $A_1 + A_2 = 10 + 20 = 30$.
• Wenn sie Freund $1$ ein Eis und Freund $2$ eine Schokolade gibt, beträgt die Gesamtfreude $A_1 + B_2 = 10 + 30 = 40$.
• Wenn sie Freund $1$ eine Schokolade und Freund $2$ ein Eis gibt, beträgt die Gesamtfreude $B_1 + A_2 = 40 + 20 = 60$.
• Wenn sie sowohl Freund $1$ als auch Freund $2$ eine Schokolade gibt, beträgt die Gesamtfreude $B_1 + B_2 = 40 + 30 = 70$.

Unter diesen $4$ Möglichkeiten ist die Gesamtfreude im letzten Fall am größten und beträgt dort $70$. Daher wird $70$ ausgegeben.

Dieses Eingabebeispiel erfüllt die Bedingungen der Teilaufgaben $3, 6, 7$.

Beispiel 3

Eingabe

1 1 0
1234
5678

Ausgabe

1234

In diesem Eingabebeispiel hat Aoi nur $1$ Freund.

Dieses Eingabebeispiel erfüllt die Bedingungen der Teilaufgaben $1, 2, 5, 6, 7$.

Beispiel 4

Eingabe

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

Ausgabe

5867599604

Beachte, dass die Ausgabe möglicherweise nicht in einen 32-Bit-Ganzzahltyp passt.

Dieses Eingabebeispiel erfüllt die Bedingungen der Teilaufgaben $4, 6, 7$.