This problem is a Mooshak version of a SPOJ problem (but with harder constraints).
Given \(N\) buildings of height \(h_1, h_2, h_3, \ldots, h_n\), the objective is to make every building have 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.
\(h_1 = h_2 = h_3 = \ldots = h_n = k\) (and \(k\) can be any number)
For convenience, all buildings are considered to be vertical piles of bricks, which are of same dimensions.
The first line of input contains an integer \(T\) which denotes number of test cases. This will be followed by \(3 \times 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 denote the heights of the buildings \(h_1, h_2, h_3, \ldots, h_n\) and the third line contains \(N\) integers \(c_1, c_2, c_3, \ldots, c_n\) which denote the cost of adding or removing one unit of brick from the corresponding building.
The output must contain T lines each line corresponding to a testcase, indicating the respective minimal cost.
| Example Input | Example Output |
2 3 1 2 3 10 100 1000 3 1 3 2 10 100 100 |
120 110 |