Contests | Virtual Contests | Problems | Submit | Runs Status | Rank List | Forum |

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 *t*_{i} time to complete. Given a schedule (i.e., an ordering of the problems), let *C*_{i} denote the finishing time of problem *i*. For example, if problem *j* is the first to be done, we would have *C*_{j} = *t*_{j} . Each problem *i* also has a given weight *w*_{i} 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 w_{1}C_{1} + w_{2}C_{2} + w_{3}C_{3}… + w_{n}C_{n}. ### 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, t_{1},t_{2},…,t_{n},(0 < t_{i} ≤ 20), *t*_{i} means the time problem *i* would take. The third line contains *n* numbers, w_{1},w_{2},…w_{n},(0 < w*i* ≤ 20), *w*_{i} 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*)w_{i}C_{i}.
### Sample Input

### Sample Output

You should design an efficient algorithm to solve this problem. That is, you are given a set of *n* problems with a processing time *t _{i}* and a weighted

Example: Suppose there are two problems: the first takes time t_{1}=2 and has weight w_{1}=12, while the second problem takes time t_{2}=3 and has weight w_{2}=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*)w_{i}C_{i}.

1 2 2 3 12 4

44

Maintance:G.D.Retop. Developer: SuperHacker, G.D.Retop