Shobon har bestämt sig för att använda en generativ AI som hjälp för att utveckla ett mjukvaruprojekt. Projektet består av $N$ uppgifter. Varje uppgift $i$ ($i = 1, 2, \dots, N$) har en förutbestämd implementeringsarbetsmängd $A_i$ och komplexitet $B_i$.

Shobon kan utföra dessa uppgifter i vilken ordning som helst. Han kan dock inte arbeta med mer än en uppgift samtidigt.

Varje uppgift $i$ ($i = 1, 2, \dots, N$) kan slutföras på ett av följande två sätt:

• Implementera uppgiften manuellt. Shobon skriver koden själv, vilket tar $A_i$ tidsenheter.
• Använd den generativa AI:n. För att få AI:n att generera korrekt kod förklarar Shobon den aktuella uppgiften samt alla tidigare slutförda uppgifter för AI:n. Låt $S$ vara summan av komplexiteterna för alla tidigare slutförda uppgifter. Att förbereda denna förklaring tar $S + B_i$ tidsenheter. AI:n slutför sedan implementeringen omedelbart, så ingen ytterligare implementeringstid krävs. Att slutföra denna uppgift med hjälp av AI:n tar alltså totalt $S + B_i$ tidsenheter.

Oavsett vilken metod som används kommer uppgiftens komplexitet $B_i$, när uppgift $i$ väl är slutförd, att inkluderas i framtida värden på $S$ när den generativa AI:n används.

Bestäm den minsta totala tid som krävs för att slutföra alla uppgifter.

Indata

Indatan består av tre rader i följande format.

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

På den första raden ges antalet uppgifter, $N$ ($1 \le N \le 2 \times 10^5$). Den andra raden innehåller $N$ heltal, $A_1, A_2, \dots, A_N$, vart och ett mellan $1$ och $10^9$ (inklusive), som representerar implementeringsarbetsmängderna för de $N$ uppgifterna. Den tredje raden innehåller $N$ heltal, $B_1, B_2, \dots, B_N$, vart och ett mellan $1$ och $10^8$ (inklusive), som representerar komplexiteterna för de $N$ uppgifterna.

Utdata

Skriv ut på en rad den minsta totala tid som krävs för att slutföra alla uppgifter.

Exempel

Indata 1

3
10 6 10
5 2 4

Utdata 1

18

Indata 2

1
4
10

Utdata 2

4

Indata 3

5
100 100 100 100 100
5 1 4 2 3

Utdata 3

35

Indata 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

Förklaring

För exempelindata 1, betrakta att använda den generativa AI:n för uppgifterna $2$ och $3$ i denna ordning, och sedan implementera uppgift $1$ manuellt.

• När uppgift $2$ påbörjas har ingen uppgift slutförts ännu. Denna uppgift tar $0 + B_2 = 2$ tidsenheter.
• När uppgift $3$ påbörjas har uppgift $2$ slutförts. Denna uppgift tar $B_2 + B_3 = 2 + 4 = 6$ tidsenheter.
• Slutligen tar det $A_1 = 10$ tidsenheter att implementera uppgift $1$ manuellt.

Alltså kan alla uppgifter slutföras på $2 + 6 + 10 = 18$ tidsenheter, vilket är det minsta möjliga.