Takahashi and Aoki have recently started trading stonks to make some money.
For the next N days, Aoki will buy some stonks in the morning. On the ith morning, he will buy Ai stonks.
Takahashi has written a script to predict the trends of the stonk market. Thus, he knows that on the ith day, he can sell a stonk for Bi yen. He can only sell stonks which were purchased on or before that day.
Takahashi wants to know the maximum amount of money they can make selling stonks (ignore the money Aoki spends buying stonks). Code a program to help him!
The first line of input contains a single integer N.
The next line of input contains N integers, representing the array A.
The last line of input contains N integers, representing the array B.
The first and only line of output should contain a single integer, denoting the maximum amount of money made selling stonks.
For all subtasks, 1 ≤ N, Ai, Bi ≤ 1000000.
Subtask 1 (20%): N ≤ 1000
Subtask 2 (15%): Ai = 1
Subtask 3 (65%): There are no more constraints.
2 8 3 2 8 4 5
9 8 7 5 4 4 8
Takahashi can sell 2 stonks on day 1, 5 stonks on day 2 and 25 stonks on day 7 for 258 yen total. This is optimal.