Tommy, Elex and Steven had a mental breakdown when they were trying to make problem S5 for the Mock CCC' 24. They thought about string algorithms, dynamic programming, graph theory, data structures, ad hoc, and ... even simulated annealing. In the end, they decided to just have a Mock CCC '24 that consists of four problems, and try harder for the Mock CCC '25.

As somebody who wants to practice and get ready for the upcoming CCC, you cannot let this happen. Therefore, you found Tommy and convinced him to create another problem for the contest. However, Tommy said he will only make the problem if you help him calculate what is the minimum time for him to make ~N~ problems. Interestingly, it is more challenging and time-consuming for Tommy to create a problem immediately after completing another one. Therefore, he occasionally takes a break between creating two problems. Specifically, Tommy needs to spend ~t_i~ minutes to complete the ~i^{th}~ problem if he takes a break.

However, if he doesn't take a break after making a problem, the time he requires for each subsequent problem before taking a break will increase by the time needed for him to create the problem he just finished. Furthermore, the length of the break that Tommy wants to make depends on the number of problems he has made. In detail, the duration of the break, after he made ~i~ problems in total, will be ~d_i~. He will also take a break upon completing all the problems, and this break is included in the total time he spent making the ~N~ problems because he cannot take part in other activities during the break.

Please help Tommy calculate the minimum time needed to make all problems.

Input Specification

The first line of input will consist of an integer, ~N~.

The second line of input will consist of ~N~ space-separated integers, ~t_1, \dots, t_N~.

The third line of input will consist of ~N~ space-separated integers, ~d_1, \dots, d_N~.

Marks Awarded	~N~	~t_i~	~d_i~
~3~ marks	~1 \leq N \leq 10^3~	~1 \leq t_i \leq 10^4~	~1 \leq d_i \leq 10^4~
~12~ marks	~1 \leq N \leq 10^6~	~1 \leq t_i \leq 10^{12}~	~1 \leq d_i \leq 10^{12}~

Output Specification

Output the minimum time needed for Tommy to create all the problems.

Sample Input 1

3
1 1 1
3 3 3

Sample Output 1

9

Explanation for Sample 1

First, Tommy will make the first question, taking him ~1~ minute. Tommy will immediately make the second problem instead of taking a break. The second problem takes ~1~ minute, but because he did not take a break, he will take an additional minute to make that problem. Tommy currently has taken ~3~ minutes. As for the last question, Tommy can once again immediately make the question instead of taking a break. He will take the one minute it requires to make the third problem. However, because he did not take a break after making the first and second problems, he will take the additional time of the first two problems to make the third problem, meaning it takes Tommy ~3~ minutes to make the third problem. So far, Tommy has made all three problems and has taken ~6~ minutes. However, he must take his final break. Because Tommy created three problems in total, he will take a ~3~ minute break, as he normally would after making the third problem, meaning Tommy has taken ~9~ minutes to make three problems. This can be shown to be the minimum possible time required for him to complete this task.

Sample Input 2

5
6 8 9 7 9
6 9 5 7 7

Sample Output 2

72