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$ 값에 포함된다.

모든 작업을 완료하는 데 필요한 최소 총 시간을 구하시오.

입력

입력은 다음 형식의 세 줄로 구성된다.

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

첫째 줄에 작업의 수 $N$이 주어진다 ($1 \le N \le 2 \times 10^5$). 둘째 줄에는 $N$개의 작업의 구현 작업량을 나타내는 $1$ 이상 $10^9$ 이하의 정수 $N$개 $A_1, A_2, \dots, A_N$이 주어진다. 셋째 줄에는 $N$개의 작업의 복잡도를 나타내는 $1$ 이상 $10^8$ 이하의 정수 $N$개 $B_1, B_2, \dots, B_N$이 주어진다.

출력

모든 작업을 완료하는 데 필요한 최소 총 시간을 한 줄에 출력한다.

예제

입력 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$만큼의 시간에 완료할 수 있으며, 이것이 가능한 최솟값이다.