Get Minimum Round Trip Cost

Given arrays departing and returning of equal length, giving the outbound and return fares on day i respectively. Choose a departure day i and a return day j, where the return must be strictly later than the departure (j > i), and find the minimum of departing[i] + returning[j]. This strict ordering constraint was filled in from public reports of the same problem.

Site constraints: 2≤n≤200000, -1000000000≤any fare≤1000000000.

输入格式

The first line contains n; the second line contains n outbound fares departing; the third line contains n return fares returning.

输出格式

Output the minimum total cost such that the return day j is strictly greater than the departure day i.

样例 1

输入：

4
1 2 3 4
4 3 2 1

输出：

2

样例 2

输入：

2
100 1
1 100

输出：

200

样例 3

输入：

3
8 1 5
7 2 9

输出：

10

样例 4

输入：

2
4 4
3 3

输出：

7

样例 5

输入：

3
-5 8 -2
7 -9 4

输出：

-14

样例 6

输入：

4
1 2 3 4
1 2 3 4

输出：

3

样例说明

Scan from right to left, maintaining the minimum of returning[i+1..n-1], pair it with departing[i], and update the answer.