冰原狼，也被称为黑狼，是一种似乎起源于德雷诺又大又壮的狼，体型几乎是普通狼的两倍这些强壮的野兽，长8-9英尺，重600-800磅，是最著名的兽人坐骑。这些巨狼和人一样高，长着长长的獠牙，看起来像能折断铁棒。他们有燃烧的红眼睛。灰狼的颜色是斑驳的灰色或黑色。脏狼在卡利姆多和马尔戈尔的北部地区茁壮成长。恶狼是高效的狼群猎手，会杀死他们抓到的任何东西。它们更喜欢成群结队地攻击，在可能的情况下包围并侧翼攻击敌人。(WOW)

来自东方王国的冒险家Matt遇到了一群可怕的狼。有N只狼排成一行（从左到右编号为1到N）。Matt必须打败他们才能生存。



一旦Matt击败了一只可怕的狼，他将受到相当于狼当前攻击的伤害。作为群居动物，每只可怕的狼$i$都可以通过$b_i$增加其相邻狼的攻击。因此，每只恐怖的狼$i$的当前攻击由两部分组成，即其基本攻击$a_i$和当前相邻狼提供的额外攻击。攻击的增加是暂时的。一旦一只狼被击败，它的相邻狼将不再受到它的额外攻击。然而，这两只狼（如果存在的话）现在将变得相邻。


例如，假设有3只可怕的狼排成一行，它们的基本攻击$a_i$分别为$（3,5,7）$。它们可以提供的额外攻击是$（8,2,0）$。因此，他们目前的攻击是$（5，13，9）$。如果Matt先击败第二只狼，他将获得13点伤害，活狼的当前攻击变为$（3,15）$。


作为一名机敏而足智多谋的冒险家，Matt可以决定他击败的可怕狼群的顺序。因此，他想知道击败所有狼群所需的最小伤害。

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

第二行包含$N$个整数$a_i（0≤a_i≤100000）$，表示每只可怕的狼的基本攻击。

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

每组测试数据一行输出，表示Matt受到的最小伤害