Background

马特（Matt）是来自东部王国的一位冒险者，某日遭遇了一群狼。这群狼共有N只，排成一列（从左到右编号为1至N）。马特必须击败所有狼才能存活。

每当马特击败一只狼时，他会受到等同于该狼当前攻击力的伤害。作为一种群居生物，每只狼i会为其相邻的狼提供额外的攻击力加成bi。因此，每只狼i的当前攻击力由两部分组成： 基础攻击力ai和来自相邻狼的额外攻击力。

这种加成是暂时的——一旦某只狼被击败，其相邻狼将不再获得它提供的加成。但此时，原本不相邻的狼可能会因中间狼的死亡而变为相邻。

例如，假设有3只狼排成一列，其基础攻击力分别为(3, 5, 7)，提供的额外攻击力分别为(8, 2, 0)。那么它们的当前攻击力为(3+2, 5+8+0, 7+2)=(5, 13, 9)。如果马特先击败第二只狼，他将受到13点伤害，存活狼的攻击力变为(3+0, 7+8)=(3, 15)。

作为一名机敏且足智多谋的冒险者，马特可以决定击败狼的顺序。因此，他希望计算出击败所有狼所需承受的最小伤害总值。

Format

Input

第一行包含一个整数T，表示测试用例的数量。

每个测试用例的第一行为一个整数N（2 ≤ N ≤ 200），表示狼的数量。

第二行包含N个整数ai（0 ≤ ai ≤ 100000），表示每只狼的基础攻击力。

第三行包含N个整数bi（0 ≤ bi ≤ 50000），表示每只狼提供的额外攻击力。

Output

对于每个测试用例，输出一行“Case #x: y”，其中x为测试用例编号（从1开始），y为马特需要承受的最小伤害总值。

Samples

2
3
3 5 7
8 2 0
10
1 3 5 7 9 2 4 6 8 10
9 4 1 2 1 2 1 4 5 1

Case #1: 17
Case #2: 74

【样例说明】 在第一个样例中，马特按从左到右的顺序击败恐狼，受到的伤害为5 + 5 + 7 = 17，这是他能承受的最小伤害。

Limitation

1s, 1024KiB for each test case.