Shobon hat beschlossen, eine generative KI einzusetzen, um bei der Entwicklung eines Softwareprojekts zu helfen. Das Projekt besteht aus $N$ Aufgaben. Jede Aufgabe $i$ ($i = 1, 2, \dots, N$) hat einen vorgegebenen Implementierungsaufwand $A_i$ und eine Komplexität $B_i$.

Shobon kann diese Aufgaben in beliebiger Reihenfolge bearbeiten. Allerdings kann er nicht an mehr als einer Aufgabe gleichzeitig arbeiten.

Jede Aufgabe $i$ ($i = 1, 2, \dots, N$) kann auf eine der folgenden zwei Arten erledigt werden:

• Die Aufgabe manuell implementieren. Shobon schreibt den Code selbst, was $A_i$ Zeiteinheiten dauert.
• Die generative KI verwenden. Damit die KI korrekten Code generiert, erklärt Shobon der KI die aktuelle Aufgabe sowie alle zuvor erledigten Aufgaben. Sei $S$ die Summe der Komplexitäten aller zuvor erledigten Aufgaben. Das Vorbereiten dieser Erklärung dauert $S + B_i$ Zeiteinheiten. Die KI schließt die Implementierung anschließend sofort ab, sodass keine zusätzliche Implementierungszeit erforderlich ist. Somit dauert das Erledigen dieser Aufgabe mithilfe der KI insgesamt $S + B_i$ Zeiteinheiten.

Unabhängig davon, welche Methode verwendet wird, wird die Komplexität $B_i$ einer Aufgabe $i$, sobald diese erledigt ist, bei zukünftigen Verwendungen der generativen KI in den Wert von $S$ einbezogen.

Bestimme die minimale Gesamtzeit, die benötigt wird, um alle Aufgaben zu erledigen.

Eingabe

Die Eingabe besteht aus drei Zeilen im folgenden Format.

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

In der ersten Zeile wird die Anzahl der Aufgaben, $N$, angegeben ($1 \le N \le 2 \times 10^5$). Die zweite Zeile enthält $N$ ganze Zahlen, $A_1, A_2, \dots, A_N$, jeweils zwischen $1$ und $10^9$ (einschließlich), die den Implementierungsaufwand der $N$ Aufgaben darstellen. Die dritte Zeile enthält $N$ ganze Zahlen, $B_1, B_2, \dots, B_N$, jeweils zwischen $1$ und $10^8$ (einschließlich), die die Komplexitäten der $N$ Aufgaben darstellen.

Ausgabe

Gib in einer Zeile die minimale Gesamtzeit aus, die benötigt wird, um alle Aufgaben zu erledigen.

Beispiele

Eingabe 1

3
10 6 10
5 2 4

Ausgabe 1

18

Eingabe 2

1
4
10

Ausgabe 2

4

Eingabe 3

5
100 100 100 100 100
5 1 4 2 3

Ausgabe 3

35

Eingabe 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

Ausgabe 4

118

Hinweis

Betrachte für die Beispieleingabe 1 die Verwendung der generativen KI für die Aufgaben $2$ und $3$ in dieser Reihenfolge und die anschließende manuelle Implementierung von Aufgabe $1$.

• Wenn Aufgabe $2$ begonnen wird, wurde noch keine Aufgabe erledigt. Diese Aufgabe dauert $0 + B_2 = 2$ Zeiteinheiten.
• Wenn Aufgabe $3$ begonnen wird, wurde Aufgabe $2$ bereits erledigt. Diese Aufgabe dauert $B_2 + B_3 = 2 + 4 = 6$ Zeiteinheiten.
• Schließlich dauert die manuelle Implementierung von Aufgabe $1$ genau $A_1 = 10$ Zeiteinheiten.

Somit können alle Aufgaben in $2 + 6 + 10 = 18$ Zeiteinheiten erledigt werden, was das mögliche Minimum ist.