Shobon on päättänyt käyttää generatiivista tekoälyä apuna ohjelmistoprojektin kehittämisessä. Projekti koostuu $N$ tehtävästä. Jokaisella tehtävällä $i$ ($i = 1, 2, \dots, N$) on ennalta määrätty toteutustyömäärä $A_i$ ja monimutkaisuus $B_i$.

Shobon voi suorittaa nämä tehtävät missä tahansa järjestyksessä. Hän ei kuitenkaan voi työskennellä useamman kuin yhden tehtävän parissa samanaikaisesti.

Jokainen tehtävä $i$ ($i = 1, 2, \dots, N$) voidaan suorittaa yhdellä seuraavista kahdesta tavasta:

• Toteuta tehtävä manuaalisesti. Shobon kirjoittaa koodin itse, mikä vie $A_i$ aikayksikköä.
• Käytä generatiivista tekoälyä. Jotta tekoäly tuottaisi oikeaa koodia, Shobon selittää tekoälylle nykyisen tehtävän sekä kaikki aiemmin valmistuneet tehtävät. Olkoon $S$ kaikkien aiemmin valmistuneiden tehtävien monimutkaisuuksien summa. Tämän selityksen valmistelu vie $S + B_i$ aikayksikköä. Tämän jälkeen tekoäly saa toteutuksen valmiiksi välittömästi, joten ylimääräistä toteutusaikaa ei tarvita. Näin ollen tämän tehtävän suorittaminen tekoälyn avulla vie yhteensä $S + B_i$ aikayksikköä.

Riippumatta siitä, kumpaa menetelmää käytetään, kun tehtävä $i$ on saatu valmiiksi, sen monimutkaisuus $B_i$ sisällytetään tuleviin $S$:n arvoihin generatiivista tekoälyä käytettäessä.

Etsi pienin mahdollinen kokonaisaika, joka tarvitaan kaikkien tehtävien suorittamiseen.

Syöte

Syöte koostuu kolmesta rivistä seuraavassa muodossa.

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

Ensimmäisellä rivillä annetaan tehtävien lukumäärä $N$ ($1 \le N \le 2 \times 10^5$). Toinen rivi sisältää $N$ kokonaislukua, $A_1, A_2, \dots, A_N$, joista jokainen on välillä $1$ ja $10^9$ (rajat mukaan lukien), ja ne kuvaavat $N$ tehtävän toteutustyömääriä. Kolmas rivi sisältää $N$ kokonaislukua, $B_1, B_2, \dots, B_N$, joista jokainen on välillä $1$ ja $10^8$ (rajat mukaan lukien), ja ne kuvaavat $N$ tehtävän monimutkaisuuksia.

Tuloste

Tulosta yhdelle riville pienin mahdollinen kokonaisaika, joka tarvitaan kaikkien tehtävien suorittamiseen.

Esimerkit

Syöte 1

3
10 6 10
5 2 4

Tuloste 1

18

Syöte 2

1
4
10

Tuloste 2

4

Syöte 3

5
100 100 100 100 100
5 1 4 2 3

Tuloste 3

35

Syöte 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

Tuloste 4

118

Huomautus

Esimerkkisyötteessä 1 tarkastellaan generatiivisen tekoälyn käyttämistä tehtäviin $2$ ja $3$ tässä järjestyksessä ja sen jälkeen tehtävän $1$ toteuttamista manuaalisesti.

• Kun tehtävä $2$ aloitetaan, yhtäkään tehtävää ei ole vielä saatu valmiiksi. Tämä tehtävä vie $0 + B_2 = 2$ aikayksikköä.
• Kun tehtävä $3$ aloitetaan, tehtävä $2$ on saatu valmiiksi. Tämä tehtävä vie $B_2 + B_3 = 2 + 4 = 6$ aikayksikköä.
• Lopuksi tehtävän $1$ toteuttaminen manuaalisesti vie $A_1 = 10$ aikayksikköä.

Näin ollen kaikki tehtävät voidaan suorittaa $2 + 6 + 10 = 18$ aikayksikössä, mikä on pienin mahdollinen aika.