题目描述

狼王，也被称为暗黑狼，是异常庞大而强大的狼。许多，如果不是全部，狼王似乎起源于德拉诺。 狼王看起来像普通的狼，但这些生物几乎是普通狼的两倍大小。这些强大的野兽，长8-9英尺，重600-800磅，是最著名的兽人坐骑。和人一样高，这些巨大的狼有着长长的长牙，看起来能咬断铁棒。它们有着燃烧的红色眼睛。狼王的颜色斑驳灰色或黑色。狼王在卡利姆多的北部地区和莫高雷地区茁壮成长。 狼王是高效的群体猎手，会杀死它们捕捉到的任何东西。它们更喜欢以群体方式攻击，包围和侧翼敌人。 —— Wowpedia，你在魔兽世界的维基指南

马特，来自东部王国的冒险家，遇到了一群狼王。有N只狼站成一排（从左到右编号为1到N）。马特必须打败它们中的所有狼才能生存。

一旦马特打败一只狼王，他将受到与狼王当前攻击力相等的伤害。作为群居动物，每只狼王i都可以增加其相邻狼的攻击力b​~i~​。因此，每只狼王i的当前攻击由两部分组成，其基本攻击ai和当前相邻狼提供的额外攻击。攻击增加是临时的。一旦一只狼被打败，其相邻狼将不再从它那里获得额外攻击。但是，这两只狼（如果存在）现在将成为彼此的相邻。

例如，假设有3只站成一排的狼王，其基本攻击ai分别为（3, 5, 7）。它们可以提供的额外攻击b~i~分别为（8, 2, 0）。因此，它们的当前攻击分别为（5, 13, 9）。如果马特首先打败第二只狼王，他将受到13点伤害，而存活的狼的当前攻击将变为（3, 15）。

作为一个警觉而足智多谋的冒险家，马特可以决定打败狼王的顺序。因此，他想知道打败所有狼王需要承受的最少伤害。

Input

第一行仅包含一个整数T，表示测试用例的数量。对于每个测试用例，第一行仅包含一个整数N（2 ≤ N ≤ 200）。

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

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

Output

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

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

Hint

在第一个示例中，马特从左到右打败狼王。他需要承受5 + 5 + 7 = 17点伤害，这是他需要承受的最少伤害。