Treść zadania

Aoi z liceum JOI postanowiła rozdać słodycze swoim znajomym.

Aoi ma $N$ znajomych, ponumerowanych od $1$ do $N$.

Aoi ma $X$ lodów oraz $Y$ czekoladek. Postanowiła rozdać wszystkim $N$ znajomym po $1$ słodyczu — albo loda, albo czekoladkę. Zagwarantowane jest przy tym, że łącznie lodów i czekoladek jest co najmniej $N$. Dzięki temu Aoi może obdarować słodyczami wszystkich swoich znajomych.

Znajomy $i$ ($1 \le i \le N$) otrzymuje $A_i$ zadowolenia, jeśli dostanie loda, oraz $B_i$ zadowolenia, jeśli dostanie czekoladkę.

Wypisz maksymalną możliwą sumę zadowolenia uzyskanego przez wszystkich znajomych Aoi.

Ograniczenia

• $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$).
• Wszystkie wartości wejściowe są liczbami całkowitymi.

Podzadania

1. ($5$ punktów) $N = 1$.
2. ($5$ punktów) $X = N$, $Y = 0$.
3. ($5$ punktów) $X = N$, $Y = N$.
4. ($25$ punktów) $X = N$, $Y = 1$.
5. ($25$ punktów) $X + Y = N$.
6. ($10$ punktów) $N \le 10$.
7. ($25$ punktów) Brak dodatkowych ograniczeń.

Wejście

Wejście podawane jest w następującym formacie:

N X Y
A_1 A_2 … A_N
B_1 B_2 … B_N

Wyjście

Wypisz maksymalną możliwą sumę zadowolenia uzyskanego przez wszystkich znajomych Aoi.

Nie wypisuj niczego poza odpowiedzią. (Nie wypisuj np. komunikatów proszących o podanie danych.)

Odnośnie formatu odpowiedzi możesz skorzystać z zadań próbnych i ich przykładowych rozwiązań.

Przykład 1

Wejście

2 1 1
10 20
40 30

Wyjście

60

Istnieją następujące $2$ sposoby rozdania słodyczy przez Aoi:

• Jeśli da loda znajomemu $1$ i czekoladkę znajomemu $2$, suma zadowolenia wyniesie $A_1 + B_2 = 10 + 30 = 40$.
• Jeśli da czekoladkę znajomemu $1$ i loda znajomemu $2$, suma zadowolenia wyniesie $B_1 + A_2 = 40 + 20 = 60$.

Spośród tych $2$ sposobów suma zadowolenia jest największa w drugim przypadku i wynosi $60$. Zatem należy wypisać $60$.

Ten przykład wejściowy spełnia ograniczenia podzadań $5, 6, 7$.

Przykład 2

Wejście

2 2 2
10 20
40 30

Wyjście

70

Istnieją następujące $4$ sposoby rozdania słodyczy przez Aoi:

• Jeśli da lody zarówno znajomemu $1$, jak i znajomemu $2$, suma zadowolenia wyniesie $A_1 + A_2 = 10 + 20 = 30$.
• Jeśli da loda znajomemu $1$ i czekoladkę znajomemu $2$, suma zadowolenia wyniesie $A_1 + B_2 = 10 + 30 = 40$.
• Jeśli da czekoladkę znajomemu $1$ i loda znajomemu $2$, suma zadowolenia wyniesie $B_1 + A_2 = 40 + 20 = 60$.
• Jeśli da czekoladki zarówno znajomemu $1$, jak i znajomemu $2$, suma zadowolenia wyniesie $B_1 + B_2 = 40 + 30 = 70$.

Spośród tych $4$ sposobów suma zadowolenia jest największa w ostatnim przypadku i wynosi $70$. Zatem należy wypisać $70$.

Ten przykład wejściowy spełnia ograniczenia podzadań $3, 6, 7$.

Przykład 3

Wejście

1 1 0
1234
5678

Wyjście

1234

W tym przykładzie wejściowym Aoi ma tylko $1$ znajomego.

Ten przykład wejściowy spełnia ograniczenia podzadań $1, 2, 5, 6, 7$.

Przykład 4

Wejście

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

Wyjście

5867599604

Zauważ, że wynik może nie zmieścić się w 32-bitowym typie całkowitoliczbowym.

Ten przykład wejściowy spełnia ograniczenia podzadań $4, 6, 7$.