冰原狼，也被称为黑狼，是一种似乎起源于德雷诺又大又壮的狼，体型几乎是普通狼的两倍这些强壮的野兽，长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受到的最小伤害

ICPC