Return Pickup

Time limit1sMemory limit1024 MB

Summary

Find the minimum time for a truck starting at position 0 to collect every house's item after its release time and return to 0.

Level: Medium7 of 10
Topics: Dynamic programming, Intervals
Solved: No attempts yet

문제

As shown in the figure below, $N$ houses are on a straight road, numbered $1$ to $N$ from left to right. The position of house $i$ ( $1 \le i \le N$ ) is $X_i$ ( $X_i > 0$ ).

A delivery company uses one truck to visit all $N$ houses and collect returned items. The truck leaves the company at position $0$ at time $0$ . House $i$ puts out its returned item at time $T_i$ . The truck moves at speed $1$ , so moving a distance $d$ takes $d$ time. If needed, the truck can stop and wait in place.

When the truck passes the position of a house with a returned item, it collects the item instantly. Collecting an item takes $0$ time. So the truck can collect the item from house $i$ if it passes position $X_i$ at time $T_i$ or later.

Given the house positions and the times when each item is put out, write a program that finds the minimum time for the truck to collect all items and return to the company.

입력

The first line contains $N$ , the number of houses with returned items.

The second line contains the positions $X_1, X_2, \cdots, X_N$ , separated by spaces.

The third line contains the times $T_1, T_2, \cdots, T_N$ at which each house puts out its item, separated by spaces.

출력

Print the minimum time for the truck to collect all items and return to the company.

제한

All given numbers are integers.
$1 \le N \le 3000$
$1 \le X_1 < X_2 < \cdots < X_N \le 10^8$
$0 \le T_i \le 10^8$ ( $1 \le i \le N$ )

Examples2

Example 1
Input
```
4
2 5 7 10
20 4 16 11
```
Expected output
```
23
```
Example 2
Input
```
3
1 2 3
3 2 1
```
Expected output
```
6
```