Shobon postanowił użyć generatywnej sztucznej inteligencji (AI), aby pomóc sobie w tworzeniu projektu programistycznego. Projekt składa się z $N$ zadań. Każde zadanie $i$ ($i = 1, 2, \dots, N$) ma z góry określony nakład pracy implementacyjnej $A_i$ oraz złożoność $B_i$.

Shobon może wykonywać te zadania w dowolnej kolejności. Nie może jednak pracować nad więcej niż jednym zadaniem naraz.

Każde zadanie $i$ ($i = 1, 2, \dots, N$) może zostać ukończone na jeden z dwóch poniższych sposobów:

• Zaimplementować zadanie ręcznie. Shobon sam pisze kod, co zajmuje $A_i$ jednostek czasu.
• Użyć generatywnej AI. Aby AI wygenerowała poprawny kod, Shobon wyjaśnia jej bieżące zadanie oraz wszystkie wcześniej ukończone zadania. Niech $S$ oznacza sumę złożoności wszystkich wcześniej ukończonych zadań. Przygotowanie tego wyjaśnienia zajmuje $S + B_i$ jednostek czasu. Następnie AI natychmiast kończy implementację, więc nie jest wymagany żaden dodatkowy czas na implementację. Tym samym ukończenie tego zadania przy użyciu AI zajmuje łącznie $S + B_i$ jednostek czasu.

Niezależnie od wybranej metody, gdy zadanie $i$ zostanie ukończone, jego złożoność $B_i$ jest wliczana do przyszłych wartości $S$ podczas korzystania z generatywnej AI.

Znajdź minimalny łączny czas potrzebny na ukończenie wszystkich zadań.

Wejście

Wejście składa się z trzech wierszy w następującym formacie.

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

W pierwszym wierszu podana jest liczba zadań $N$ ($1 \le N \le 2 \times 10^5$). Drugi wiersz zawiera $N$ liczb całkowitych $A_1, A_2, \dots, A_N$, każda z przedziału od $1$ do $10^9$ włącznie, oznaczających nakłady pracy implementacyjnej dla poszczególnych $N$ zadań. Trzeci wiersz zawiera $N$ liczb całkowitych $B_1, B_2, \dots, B_N$, każda z przedziału od $1$ do $10^8$ włącznie, oznaczających złożoności poszczególnych $N$ zadań.

Wyjście

Wypisz w jednym wierszu minimalny łączny czas potrzebny na ukończenie wszystkich zadań.

Przykład

Wejście 1

3
10 6 10
5 2 4

Wyjście 1

18

Wejście 2

1
4
10

Wyjście 2

4

Wejście 3

5
100 100 100 100 100
5 1 4 2 3

Wyjście 3

35

Wejście 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

Wyjście 4

118

Uwagi

Dla pierwszego przykładu wejściowego rozważmy użycie generatywnej AI dla zadań $2$ i $3$ w tej kolejności, a następnie ręczne zaimplementowanie zadania $1$.

• Gdy rozpoczynane jest zadanie $2$, żadne zadanie nie zostało jeszcze ukończone. Zadanie to zajmuje $0 + B_2 = 2$ jednostki czasu.
• Gdy rozpoczynane jest zadanie $3$, zadanie $2$ zostało już ukończone. Zadanie to zajmuje $B_2 + B_3 = 2 + 4 = 6$ jednostek czasu.
• Na koniec ręczna implementacja zadania $1$ zajmuje $A_1 = 10$ jednostek czasu.

Wszystkie zadania można zatem ukończyć w czasie $2 + 6 + 10 = 18$ jednostek czasu, co jest najmniejszą możliwą wartością.