Excruciating Elevators

문제

It is the 25th of May, 3025. The EEMCS building at TU Delft has grown to ${10}^{6}10^6$ floors beyond the ground floor! The floors are now numbered $0,1,\dots ,{10}^{6}0,1,\backslash ldots,10^6$, but there are still only four elevators. Moreover, the elevators have malfunctioned and are currently turned off. As employee of the Building Ascension Plans Company, you are tasked to fix the elevators.

You first have to order some components, which will take a month to arrive at the ground floor. After collecting the components, you must visit $nn$ floors $f_1,\dots ,f_{n}f\_1,\backslash ldots,f\_n$ in order. At each floor $f_{i}f\_i$, you must replace some component, which takes $t_{i}t\_i$ seconds. After replacing the final component, the elevators will be fixed.

The stairs have long been removed, since people got tired of walking up millions of flights of stairs. You thus have to use the elevators to travel between the floors. You can turn on the elevators, but when you turn one on, you can no longer turn it off. Once turned on, an elevator will move up and down between floors $00$ and ${10}^{6}10^6$ indefinitely. The elevators move at a speed of one floor every second without stopping, but you are agile enough to enter and exit.

You know exactly when the components will arrive. In the meantime, you can determine when to turn on each elevator. This timing determines the starting configuration of each elevator when the components arrive. Since you have a month, you can enforce any arbitrary starting configuration of the elevators. What is the minimum possible time to fix the elevators?

As an example, consider the first sample input. You can ensure one elevator starts at ground floor going up, and another starts at floor $750000750\backslash ,000$ going up. Entering the former elevator immediately, you arrive at floor $600000600\backslash ,000$ after $600000600\backslash ,000$ seconds. After $5000050\backslash ,000$ more seconds, you finish replacing the component at floor $600000600\backslash ,000$. In the meantime, the latter elevator reached the top floor after $250000250\backslash ,000$ seconds, when it started going down. Now, $400000400\backslash ,000$ seconds later, this elevator is at floor $600000600\backslash ,000$ going down. You can enter this elevator immediately and exit $200000200\backslash ,000$ seconds later at floor $400000400\backslash ,000$. Finally, after $150000150\backslash ,000$ seconds, you finish replacing the component at floor $400000400\backslash ,000$, and the elevators are fixed! The total time is $600000+50000+200000+150000=1000000600\backslash ,000+50\backslash ,000+200\backslash ,000+150\backslash ,000=1\backslash ,000\backslash ,000$ seconds.

입력

The input consists of:

• One line with an integer $nn$ ($1\le n\le 351\backslash leq\; n\backslash leq\; 35$), the number of floors to visit.
• One line with $nn$ integers $f_1,\dots ,f_{n}f\_1,\backslash ldots,f\_n$ ($0\le f_i\le {10}^{6}0\backslash leq\; f\_i\backslash leq10^6$ for each $ii$), the numbers of the floors you must visit.
• One line with $nn$ integers $t_1,\dots ,t_{n}t\_1,\backslash ldots,t\_n$ ($1\le t_i\le {10}^{9}1\backslash leq\; t\_i\backslash leq10^9$ for each $ii$), the necessary time spent on each floor in seconds.

No two consecutive floors $f_i,f_{i+1}f\_i,f\_\{i+1\}$ are equal, and $f_{1}f\_1$ is non-zero.

출력

Output the minimum possible time in seconds to fix the elevators after the components have arrived and you start at the ground floor.

2
600000 400000
50000 150000

1000000

10
1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1

4000012