The Queue
In the ABT ("Amortized Binary Trees") market, there are customers standing in a queue in positions from to . The time needed for the cashier to serve the -th customer is .
The time that a customer needs to spend in a queue is the sum of times needed for the cashier to serve all the customers before them, added to the time needed to serve this customer. That is, in a queue of people with the times for each person are , and respectively.
To minimize the sum of times needed for customers to stand in a queue before they get served, they agreed to be reordered. However, the -th customer does not want to be moved more than positions back from their original position (however, they are fine with moving forward for any number of positions). What is the minimal sum of times these customers can reach?
Input
The first line consists of one integer — the number of customers in the queue.
The second line contains integers — the amount of time needed for the cashier to serve each customer.
The third line contains integers — the maximum number of positions which each customer is agreed to move back.
Output
In the only line, you need to output the minimal sum of waiting times that can be reached.
Examples
Note
In the first sample, there are two valid ways of rearranging the customers:
The -st one, the -nd one and the -rd one (not moving anyone);
The -nd one, the -st one and the -rd one;
The -nd one, the -rd one and the -st one;
The -rd one, the -nd one and the -st one.
The sums of times in these cases are:
;
;
;
.
As we can see, the best answer here is . It can be shown that there no other possible arrangements of people in this queue.
In the second sample, both people can be at any position, so both their possible arrangements are valid and they give equal answers of .
In the third sample, it can be shown that you cannot move any of the people, and their only valid arrangement is the initial one. The sum of times that people will be waiting in this queue is .
Scoring
( points): for all ;
( points): ;
( points): ;
( points): for all ;
( points): ;
( points): for all ;
( points): no additional constraints.