Shobon a décidé d'utiliser une IA générative pour l'aider à développer un projet logiciel. Le projet consiste en $N$ tâches. Chaque tâche $i$ ($i = 1, 2, \dots, N$) possède une charge de travail d'implémentation prédéterminée $A_i$ et une complexité $B_i$.

Shobon peut effectuer ces tâches dans n'importe quel ordre. Cependant, il ne peut pas travailler sur plus d'une tâche en même temps.

Chaque tâche $i$ ($i = 1, 2, \dots, N$) peut être accomplie de l'une des deux manières suivantes :

• Implémenter la tâche manuellement. Shobon écrit le code lui-même, ce qui prend $A_i$ unités de temps.
• Utiliser l'IA générative. Pour que l'IA génère un code correct, Shobon explique à l'IA la tâche actuelle ainsi que toutes les tâches précédemment accomplies. Soit $S$ la somme des complexités de toutes les tâches précédemment accomplies. La préparation de cette explication prend $S + B_i$ unités de temps. L'IA termine ensuite l'implémentation instantanément, de sorte qu'aucun temps d'implémentation supplémentaire n'est requis. Ainsi, accomplir cette tâche en utilisant l'IA prend un total de $S + B_i$ unités de temps.

Quelle que soit la méthode utilisée, une fois la tâche $i$ accomplie, sa complexité $B_i$ est incluse dans les futures valeurs de $S$ lors de l'utilisation de l'IA générative.

Trouvez le temps total minimum requis pour accomplir toutes les tâches.

Entrée

L'entrée se compose de trois lignes au format suivant.

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

Sur la première ligne est donné le nombre de tâches, $N$ ($1 \le N \le 2 \times 10^5$). La deuxième ligne contient $N$ entiers, $A_1, A_2, \dots, A_N$, chacun compris entre $1$ et $10^9$ inclus, représentant les charges de travail d'implémentation des $N$ tâches. La troisième ligne contient $N$ entiers, $B_1, B_2, \dots, B_N$, chacun compris entre $1$ et $10^8$ inclus, représentant les complexités des $N$ tâches.

Sortie

Affichez sur une ligne le temps total minimum requis pour accomplir toutes les tâches.

Exemples

Entrée 1

3
10 6 10
5 2 4

Sortie 1

18

Entrée 2

1
4
10

Sortie 2

4

Entrée 3

5
100 100 100 100 100
5 1 4 2 3

Sortie 3

35

Entrée 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

Sortie 4

118

Remarque

Pour l'entrée d'exemple 1, considérons l'utilisation de l'IA générative pour les tâches $2$ et $3$ dans cet ordre, puis l'implémentation manuelle de la tâche $1$.

• Lorsque la tâche $2$ commence, aucune tâche n'a encore été accomplie. Cette tâche prend $0 + B_2 = 2$ unités de temps.
• Lorsque la tâche $3$ commence, la tâche $2$ a été accomplie. Cette tâche prend $B_2 + B_3 = 2 + 4 = 6$ unités de temps.
• Enfin, implémenter manuellement la tâche $1$ prend $A_1 = 10$ unités de temps.

Ainsi, toutes les tâches peuvent être accomplies en $2 + 6 + 10 = 18$ unités de temps, ce qui est le minimum possible.