Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

2780.   Homework
Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 717   Accepted Runs: 256



Doing homework often makes students understand knowledge deeply. As a student of UESTC, WCM usually has much homework to do. Every day he gets a set of problems from teachers. Problem i will take ti time to complete. Given a schedule (i.e., an ordering of the problems), let Ci denote the finishing time of problem i. For example, if problem j is the first to be done, we would have Cj = tj . Each problem i also has a given weight wi that represents its importance to the student's mastering of the correlative knowledge. He wants to order the problems to minimize the weighted sum of the completion times, namely w1C1 + w2C2 + w3C3… + wnCn.

You should design an efficient algorithm to solve this problem. That is, you are given a set of n problems with a processing time ti and a weighted wi for each problem. You want to order the problems so as to minimize the weighted sum of the completion times, Σ(i=1..n)wiCi.

Example: Suppose there are two problems: the first takes time t1=2 and has weight w1=12, while the second problem takes time t2=3 and has weight w2=4. Then doing problem 1 first would yield a weighted completion time of 12*2+4*5=44, while doing the second problem first would yield a larger weighted completion time of 4*3+12*5=72.Apparently, 44 is the minimum of the weighted sum of completion times, Σ(i=1..n)wiCi.

Input

The input contains an integer T on the first line, which indicates the number of test cases. Each test case consists of three lines. The first line contains one integer n,(0 < n ≤ 1000),which means the number of the problems. The second line contains n numbers, t1,t2,…,tn,(0 < ti ≤ 20), ti means the time problem i would take. The third line contains n numbers, w1,w2,…wn,(0 < wi ≤ 20), wi means the weight of problem i.

Output

For each test case output one line containing a single integer, which represents the minimum of the weighted sum of the completion times, Σ(i=1..n)wiCi.

Sample Input

1
2
2 3
12 4

Sample Output

44


Source: The 5th UESTC Programming Contest Preliminary
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:G.D.Retop. Developer: SuperHacker, G.D.Retop