## KOPC12A - K12 - Building Construction

no tags

Given N buildings of height h1,h2,h3...hn, 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 re-constructing the buildings such that the N buildings satisfy

h1=h2=h3=..=hn=k ( k can be any number).

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

Given N buildings of height h1,h2,h3...hn, 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 re-constructing the buildings such that the N buildings satisfy
h1=h2=h3=..=hn=k ( k can be any number).

### Input

The first line of input contains an integer T which denotes number of test cases .This will be followed by 3*T lines , 3 lines per test case. The first line of each test case contains an integer n and the  second line contains n integers which denotes the heights of the buildings [h1,h2,h3....hn] and the third line contains n integers [c1,c2,c3...cn] which denotes the cost of adding or removing one unit of brick from the corresponding building.

T<=15;n<=10000;0<=Hi<=10000;0<=Ci<=10000;

### Output

The output must contain T lines each line corresponding to a testcase.

### Example

`Input:`
```1
3
1 2 3
10 100 1000

Output:```
`120`

 < Previous 1 2 3 4 Next > LeppyR64: 2012-04-03 04:13:13 K=3 All n buildings must be the same height. Height of zero doesn't decrease n. removing from one building is an action on that building. Adding it to another is another action on the other building. 10 to add a brick to the frst building twice is 20. 100 to add a brick to second building is 120. Dejan Tomic: 2012-04-02 22:56:11 Wait, I think I understand. Does the sum of all heights has to be the same at the end? If the answer is NO then I understand everything now... Dejan Tomic: 2012-04-02 21:37:02 I just do not understand the test case. Why is the solution 120? If all 3 buildings should be of height 2, the cost would be 1010 (removing a brick from the 3rd building + adding to 1st). If we however want 2 buildings of height 3, this could be accomplished by removing the only brick from the 1st building and adding it to the 2nd. But that would cost 110, not 120. So how would you explain the solution of 120?