Shobon hefur ákveðið að nota spunagreind (generative AI) til að hjálpa við þróun á hugbúnaðarverkefni. Verkefnið samanstendur af $N$ verkþáttum. Hver verkþáttur $i$ ($i = 1, 2, \dots, N$) hefur fyrirfram ákveðið innleiðingarvinnuframlag $A_i$ og flækjustig $B_i$.

Shobon getur unnið þessa verkþætti í hvaða röð sem er. Hins vegar getur hann ekki unnið að fleiri en einum verkþætti í einu.

Hvern verkþátt $i$ ($i = 1, 2, \dots, N$) má klára á annan hvorn af eftirfarandi tveimur háttum:

• Innleiða verkþáttinn handvirkt. Shobon skrifar kóðann sjálfur, sem tekur $A_i$ tímaeiningar.
• Nota spunagreindina. Til að fá gervigreindina til að búa til réttan kóða útskýrir Shobon núverandi verkþátt og alla áður kláraða verkþætti fyrir gervigreindinni. Látum $S$ vera summu flækjustiga allra verkþátta sem þegar hafa verið kláraðir. Að undirbúa þessa útskýringu tekur $S + B_i$ tímaeiningar. Gervigreindin lýkur þá innleiðingunni samstundis, svo enginn viðbótartími fer í innleiðinguna. Þannig tekur samtals $S + B_i$ tímaeiningar að klára þennan verkþátt með gervigreindinni.

Óháð því hvor aðferðin er notuð, þá bætist flækjustigið $B_i$ við framtíðargildi $S$ þegar spunagreindin er notuð um leið og verkþætti $i$ er lokið.

Finnið lágmarks heildartíma sem þarf til að klára alla verkþættina.

Inntak

Inntakið samanstendur af þremur línum á eftirfarandi sniði.

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

Í fyrstu línunni er fjöldi verkþátta, $N$, gefinn ($1 \le N \le 2 \times 10^5$). Önnur línan inniheldur $N$ heiltölur, $A_1, A_2, \dots, A_N$, hver á bilinu $1$ til $10^9$, báðar tölur meðtaldar, sem tákna innleiðingarvinnuframlag verkþáttanna $N$. Þriðja línan inniheldur $N$ heiltölur, $B_1, B_2, \dots, B_N$, hver á bilinu $1$ til $10^8$, báðar tölur meðtaldar, sem tákna flækjustig verkþáttanna $N$.

Úttak

Skrifið út í einni línu lágmarks heildartíma sem þarf til að klára alla verkþættina.

Dæmi

Inntak 1

3
10 6 10
5 2 4

Úttak 1

18

Inntak 2

1
4
10

Úttak 2

4

Inntak 3

5
100 100 100 100 100
5 1 4 2 3

Úttak 3

35

Inntak 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

Úttak 4

118

Athugasemd

Fyrir sýnidæmi 1, athugum að nota spunagreindina fyrir verkþætti $2$ og $3$ í þessari röð, og innleiða síðan verkþátt $1$ handvirkt.

• Þegar verkþáttur $2$ hefst hefur enginn verkþáttur verið kláraður enn. Þessi verkþáttur tekur $0 + B_2 = 2$ tímaeiningar.
• Þegar verkþáttur $3$ hefst hefur verkþáttur $2$ verið kláraður. Þessi verkþáttur tekur $B_2 + B_3 = 2 + 4 = 6$ tímaeiningar.
• Að lokum tekur handvirk innleiðing á verkþætti $1$ alls $A_1 = 10$ tímaeiningar.

Þannig má klára alla verkþættina á $2 + 6 + 10 = 18$ tímaeiningum, sem er minnsta mögulega gildið.