3458. Cards Game (Large)

输入格式

The first line of the input contains an integer $T$, the number of test cases. $T$ test cases follow; each test case consists of three lines:

First line of the each test case will contain an integer $N$.

1. The first line contains a positive integer $N$: the number of cards in the box.
2. The second line contains a list of $N$ positive integers $R_i$; the $i$-th of these represents the red number on the $i$-th card.
3. The third line contains a list of $N$ positive integers $B_i$; the $i$-th of these represents the blue number on the $i$-th card.

Limits:

• $1 \le T \le 100, 1 \le R_i \le 10^9, 1 \le B_i \le 10^9$.
• Small dataset: $2 \le N \le 5$.
• Large dataset: $2 \le N \le 100$.

输出格式

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum possible total that Akki can attain, if he plays optimally.

2
2
1 2
3 3
3
1 101 501
3 2 3

Case #1: 1
Case #2: 5

提示

In Sample Case #1, Akki has only one move in which he picks up the available cards and has two options.

1. He can choose red number from the first card and blue number from the second card to add 1 ^ 3 = 2 to the total.
2. He can choose red number from the second card and blue number from the first card to add 2 ^ 3 = 1 to the total.
   The second option is better and the answer is 1.

In Sample Case #2, one optimal strategy is to take the red number from first card and the blue number from second card, add 1 ^ 2 = 3 to the total, and return first card to the box. Then, take the red number from first card and the blue number from third card, add 1 ^ 3 = 2 to the total, and return either of the cards to the box. The final total is 5.