Shobon はソフトウェアプロジェクトの開発を支援させるために生成 AI を使うことにした．このプロジェクトは $N$ 個のタスクからなる．各タスク $i$（$i = 1, 2, \dots, N$）には，あらかじめ定められた実装作業量 $A_i$ と複雑さ $B_i$ がある．

Shobon はこれらのタスクを任意の順序で進めることができる．ただし，同時に複数のタスクに取り組むことはできない．

各タスク $i$（$i = 1, 2, \dots, N$）は，次のいずれか一方の方法で完了できる：

• 手動でタスクを実装する． Shobon が自分でコードを書く．これには $A_i$ 単位時間がかかる．
• 生成 AI を使う． AI に正しいコードを生成させるため，Shobon は現在のタスクおよびこれまでに完了したすべてのタスクについて AI に説明する．これまでに完了したすべてのタスクの複雑さの総和を $S$ とする．この説明の準備には $S + B_i$ 単位時間がかかる．その後，AI は瞬時に実装を完了するため，追加の実装時間はかからない．したがって，AI を使ってこのタスクを完了するには合計で $S + B_i$ 単位時間がかかる．

どちらの方法を使った場合でも，タスク $i$ が完了すると，その複雑さ $B_i$ はそれ以降に生成 AI を使う際の $S$ の値に含まれるようになる．

すべてのタスクを完了するのに必要な合計時間の最小値を求めよ．

入力

入力は以下の形式の 3 行からなる．

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

1 行目にはタスクの個数 $N$ が与えられる（$1 \le N \le 2 \times 10^5$）．2 行目には $N$ 個の整数 $A_1, A_2, \dots, A_N$ が与えられ，それぞれ $1$ 以上 $10^9$ 以下であり，$N$ 個のタスクの実装作業量を表す．3 行目には $N$ 個の整数 $B_1, B_2, \dots, B_N$ が与えられ，それぞれ $1$ 以上 $10^8$ 以下であり，$N$ 個のタスクの複雑さを表す．

出力

すべてのタスクを完了するのに必要な合計時間の最小値を 1 行に出力せよ．

入出力例

入力 1

3
10 6 10
5 2 4

出力 1

18

入力 2

1
4
10

出力 2

4

入力 3

5
100 100 100 100 100
5 1 4 2 3

出力 3

35

入力 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

出力 4

118

注記

入出力例 1 において，タスク $2$ とタスク $3$ にこの順で生成 AI を使い，最後にタスク $1$ を手動で実装することを考える．

• タスク $2$ を開始した時点では，まだどのタスクも完了していない．このタスクには $0 + B_2 = 2$ 単位時間がかかる．
• タスク $3$ を開始した時点では，タスク $2$ が完了している．このタスクには $B_2 + B_3 = 2 + 4 = 6$ 単位時間がかかる．
• 最後に，タスク $1$ を手動で実装するのに $A_1 = 10$ 単位時間がかかる．

したがって，すべてのタスクを $2 + 6 + 10 = 18$ 単位時間で完了でき，これが可能な最小値である．