{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e狼王,也被称为暗黑狼,是异常庞大而强大的狼。许多,如果不是全部,狼王似乎起源于德拉诺。\u003cbr\u003e狼王看起来像普通的狼,但这些生物几乎是普通狼的两倍大小。这些强大的野兽,长8-9英尺,重600-800磅,是最著名的兽人坐骑。和人一样高,这些巨大的狼有着长长的长牙,看起来能咬断铁棒。它们有着燃烧的红色眼睛。狼王的颜色斑驳灰色或黑色。狼王在卡利姆多的北部地区和莫高雷地区茁壮成长。\u003cbr\u003e狼王是高效的群体猎手,会杀死它们捕捉到的任何东西。它们更喜欢以群体方式攻击,包围和侧翼敌人。\u003cbr\u003e —— Wowpedia,你在魔兽世界的维基指南\u003cbr\u003e\u003cbr\u003e马特,来自东部王国的冒险家,遇到了一群狼王。有N只狼站成一排(从左到右编号为1到N)。马特必须打败它们中的所有狼才能生存。\u003cbr\u003e\u003cbr\u003e一旦马特打败一只狼王,他将受到与狼王当前攻击力相等的伤害。作为群居动物,每只狼王i都可以增加其相邻狼的攻击力b\u003csub\u003ei\u003c/sub\u003e。因此,每只狼王i的当前攻击由两部分组成,其基本攻击ai和当前相邻狼提供的额外攻击。攻击增加是临时的。一旦一只狼被打败,其相邻狼将不再从它那里获得额外攻击。但是,这两只狼(如果存在)现在将成为彼此的相邻。\u003cbr\u003e\u003cbr\u003e例如,假设有3只站成一排的狼王,其基本攻击ai分别为(3, 5, 7)。它们可以提供的额外攻击b\u003csub\u003ei\u003c/sub\u003e分别为(8, 2, 0)。因此,它们的当前攻击分别为(5, 13, 9)。如果马特首先打败第二只狼王,他将受到13点伤害,而存活的狼的当前攻击将变为(3, 15)。\u003cbr\u003e\u003cbr\u003e作为一个警觉而足智多谋的冒险家,马特可以决定打败狼王的顺序。因此,他想知道打败所有狼王需要承受的最少伤害。\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"第一行仅包含一个整数T,表示测试用例的数量。对于每个测试用例,第一行仅包含一个整数N(2 ≤ N ≤ 200)。\u003cbr\u003e\u003cbr\u003e第二行包含N个整数ai(0 ≤ ai ≤ 100000),表示每只狼王的基本攻击力。\u003cbr\u003e\u003cbr\u003e第三行包含N个整数bi(0 ≤ bi ≤ 50000),表示每只狼王可以提供的额外攻击力。"}},{"title":"Output","value":{"format":"HTML","content":"对于每个测试用例,输出一行“Case #x: y”,其中x是案例编号(从1开始),y是马特需要承受的最少伤害。\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3\r\n3 5 7\r\n8 2 0\r\n10\r\n1 3 5 7 9 2 4 6 8 10\r\n9 4 1 2 1 2 1 4 5 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 17\r\nCase #2: 74\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"在第一个示例中,马特从左到右打败狼王。他需要承受5 + 5 + 7 \u003d 17点伤害,这是他需要承受的最少伤害。"}}]}