Problem Description

You have $10^9$ barns arranged in a line from left to right. You want to place $n$ cows in these barns. The problem is that your cows are very aggressive and will start a fight if there are other cows nearby. Specifically, the attack range of the $i$-th cow is $(a_i, b_i)$, which means that if there are cows in any of the $a_i$ barns to its left or the $b_i$ barns to its right, it will start a fight.

You want to keep a continuous segment of barns and sell the rest. What is the minimum number of barns you need to keep to ensure that there is at least one way to place all $n$ cows in the remaining barns without any cow starting a fight?

Input Format

The first line contains a positive integer $n$.
The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$.
The third line contains $n$ positive integers $b_1, b_2, \dots, b_n$.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

2
1 2
1 2

Sample Output #1

4

Sample Input #2

3
1 2 3
3 2 1

Sample Output #2

7

Notes

Sample 1 Explanation

Keep the 1st, 2nd, 3rd, and 4th barns and place the two cows in the 1st and 4th barns.

Data Size and Constraints

• For $20\%$ of the data, $n = 2$.
• For another $20\%$ of the data, $n = 3$.
• For $80\%$ of the data, $n \leq 8$.
• For all test cases, $1 \leq n \leq 9$ and $1 \leq a_i, b_i \leq 10^3$.

见题面 Input 部分

见题面 Output 部分