Shobon ha deciso di utilizzare un'IA generativa per aiutarsi a sviluppare un progetto software. Il progetto è composto da $N$ compiti. Ogni compito $i$ ($i = 1, 2, \dots, N$) ha un carico di lavoro di implementazione predeterminato $A_i$ e una complessità $B_i$.

Shobon può procedere con questi compiti in qualsiasi ordine. Tuttavia, non può lavorare su più di un compito contemporaneamente.

Ogni compito $i$ ($i = 1, 2, \dots, N$) può essere completato in uno dei due modi seguenti:

• Implementare il compito manualmente. Shobon scrive il codice da solo, impiegando $A_i$ unità di tempo.
• Usare l'IA generativa. Affinché l'IA generi codice corretto, Shobon spiega all'IA il compito attuale e tutti i compiti completati in precedenza. Sia $S$ la somma delle complessità di tutti i compiti completati in precedenza. Preparare questa spiegazione richiede $S + B_i$ unità di tempo. L'IA termina quindi l'implementazione istantaneamente, perciò non è richiesto alcun tempo di implementazione aggiuntivo. Pertanto, completare questo compito usando l'IA richiede in totale $S + B_i$ unità di tempo.

Indipendentemente dal metodo utilizzato, una volta completato il compito $i$, la sua complessità $B_i$ viene inclusa nei valori futuri di $S$ quando si utilizza l'IA generativa.

Trova il tempo totale minimo necessario per completare tutti i compiti.

Dati di input

L'input è composto da tre righe nel seguente formato.

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

Nella prima riga viene dato il numero di compiti, $N$ ($1 \le N \le 2 \times 10^5$). La seconda riga contiene $N$ interi, $A_1, A_2, \dots, A_N$, ciascuno compreso tra $1$ e $10^9$ inclusi, che rappresentano i carichi di lavoro di implementazione degli $N$ compiti. La terza riga contiene $N$ interi, $B_1, B_2, \dots, B_N$, ciascuno compreso tra $1$ e $10^8$ inclusi, che rappresentano le complessità degli $N$ compiti.

Dati di output

Stampa su una riga il tempo totale minimo necessario per completare tutti i compiti.

Esempi

Input 1

3
10 6 10
5 2 4

Output 1

18

Input 2

1
4
10

Output 2

4

Input 3

5
100 100 100 100 100
5 1 4 2 3

Output 3

35

Input 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

Output 4

118

Note

Per l'Input di esempio 1, si consideri l'uso dell'IA generativa per i compiti $2$ e $3$ in quest'ordine, e poi l'implementazione manuale del compito $1$.

• Quando viene avviato il compito $2$, nessun compito è stato ancora completato. Questo compito richiede $0 + B_2 = 2$ unità di tempo.
• Quando viene avviato il compito $3$, il compito $2$ è stato completato. Questo compito richiede $B_2 + B_3 = 2 + 4 = 6$ unità di tempo.
• Infine, implementare manualmente il compito $1$ richiede $A_1 = 10$ unità di tempo.

Pertanto, tutti i compiti possono essere completati in $2 + 6 + 10 = 18$ unità di tempo, che è il minimo possibile.