Shobon har bestemt seg for å bruke en generativ AI som hjelp til å utvikle et programvareprosjekt. Prosjektet består av $N$ oppgaver. Hver oppgave $i$ ($i = 1, 2, \dots, N$) har en forhåndsbestemt implementeringsarbeidsmengde $A_i$ og kompleksitet $B_i$.

Shobon kan utføre disse oppgavene i hvilken som helst rekkefølge. Han kan imidlertid ikke jobbe med mer enn én oppgave om gangen.

Hver oppgave $i$ ($i = 1, 2, \dots, N$) kan fullføres på en av følgende to måter:

• Implementere oppgaven manuelt. Shobon skriver koden selv, noe som tar $A_i$ tidsenheter.
• Bruke den generative AI-en. For å få AI-en til å generere riktig kode forklarer Shobon den nåværende oppgaven og alle tidligere fullførte oppgaver til AI-en. La $S$ være summen av kompleksitetene til alle tidligere fullførte oppgaver. Å forberede denne forklaringen tar $S + B_i$ tidsenheter. AI-en fullfører deretter implementeringen umiddelbart, så ingen ekstra implementeringstid er nødvendig. Dermed tar det totalt $S + B_i$ tidsenheter å fullføre denne oppgaven ved hjelp av AI-en.

Uansett hvilken metode som brukes, vil kompleksiteten $B_i$ bli inkludert i fremtidige verdier av $S$ ved bruk av den generative AI-en så snart oppgave $i$ er fullført.

Finn den minimale totale tiden som kreves for å fullføre alle oppgavene.

Inndata

Inndataen består av tre linjer på følgende format.

$$ \begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \\ &B_1 \ B_2 \ \dots \ B_N \end{aligned} $$

På den første linjen gis antall oppgaver, $N$ ($1 \le N \le 2 \times 10^5$). Den andre linjen inneholder $N$ heltall, $A_1, A_2, \dots, A_N$, hvert mellom $1$ og $10^9$, inkludert, som representerer implementeringsarbeidsmengdene for de $N$ oppgavene. Den tredje linjen inneholder $N$ heltall, $B_1, B_2, \dots, B_N$, hvert mellom $1$ og $10^8$, inkludert, som representerer kompleksitetene til de $N$ oppgavene.

Utdata

Skriv ut på én linje den minimale totale tiden som kreves for å fullføre alle oppgavene.

Eksempler

Inndata 1

3
10 6 10
5 2 4

Utdata 1

18

Inndata 2

1
4
10

Utdata 2

4

Inndata 3

5
100 100 100 100 100
5 1 4 2 3

Utdata 3

35

Inndata 4

12
18 7 25 12 30 5 16 22 9 28 14 20
6 11 2 8 1 13 5 3 10 4 9 7

Utdata 4

118

Merk

For eksempel 1, betrakt å bruke den generative AI-en for oppgave $2$ og $3$ i denne rekkefølgen, og deretter implementere oppgave $1$ manuelt.

• Når oppgave $2$ startes, er ingen oppgave fullført ennå. Denne oppgaven tar $0 + B_2 = 2$ tidsenheter.
• Når oppgave $3$ startes, er oppgave $2$ fullført. Denne oppgaven tar $B_2 + B_3 = 2 + 4 = 6$ tidsenheter.
• Til slutt tar det $A_1 = 10$ tidsenheter å implementere oppgave $1$ manuelt.

Dermed kan alle oppgavene fullføres på $2 + 6 + 10 = 18$ tidsenheter, som er det minste mulige.