eolymp
bolt
Try our new interface for solving problems
Problems

Building Construction

Building Construction

Time limit 1 second
Memory limit 128 MiB

Given n buildings of height h_1, h_2, ..., h_n, the objective is to make every building has equal height. This can be done by removing bricks from a building or adding some bricks to a building. Removing a brick or adding a brick is done at certain cost which will be given along with the heights of the buildings. Find the minimal cost at which you can make the buildings look beautiful by reconstructing the buildings such that the n buildings satisfy h_1 = h_2 = ... = h_n = k\: (k can be any non-negative integer).

For convenience, all buildings are considered to be vertical piles of bricks, which are of same dimensions.

Input data

The first line contains number of buildings n\:(n \le 10^5). The second line contains n integers which denotes the heights of the buildings h_1, h_2, ..., h_n\:(0 \le h_i \le 10^4). The third line contains n integers c_1, c_2, ..., c_n\:(0 \le c_i \le 10^4) which denotes the cost of adding or removing one unit of brick from the corresponding building.

Output data

Print the minimal cost to make all the buildings look beautiful.

Examples

Input example #1
4
2 3 1 4
10 20 30 40
Output example #1
110
Input example #2
3
1 2 3
10 100 1000
Output example #2
120
Author Michael Medvediev