You have enrolled in an elite university that has a rank system. There are a total of N ranks starting from rank 1 to rank N. Rank N students get special priveleges, one of them being that they don't need to pay any fees. New students start from Rank 1. Naturally, you want to reach Rank N too. To reach rank i, you need to study some specific courses for d_i days. Each day, the university charges you based on your previous rank (Lets say you have to pay cost_i per day if your current rank is i). Note that you can directly do the courses for rank N when you are on rank 1, but then for d_N days you would have to pay the fees that rank 1 students need to pay. You want to reach rank N by spending minimum amount of money. How much do you need to spend?

Input:
First line contains value of N
Next line contains N numbers where the ith number represents cost_i
Next line contains N numbers where the ith number represents d_i
It is guaranteed that d_1 = 0 and cost_N = 0

Output:
Print one number, the minimum cost to reach rank N

Constraints:
1 <= N <= 5000
1 <= cost_i, d_i <= 10^5
For two numbers 1 <= i < j <= N
cost_j < cost_i
d_j > d_i       

i.,e As your rank keeps increasing, the fees payable by you decreases but the number of days you need to study to achieve that rank increases.

Sample Input 1:
5
5 4 3 2 0
0 2 3 4 5
Output:
25