题目描述

有 $n$ 头狼排成一排，每只狼两个属性，攻击力 $a_i$ 和加成值 $b_i$ ，狼的实际攻击力等于自身攻击力加相邻狼的加成值，被杀死之后的狼对相邻的狼的攻击力的加成会被取消，同时，原先与被杀死的狼相邻的两头狼会变成相邻的狼。问杀死所有狼受到的伤害值最小是。

输入格式

多组输入，第一行一个 $T$

每组输入一个 $n (n \le 200)$

输入 $n$ 个数，代表每只狼的攻击力 $(0\le a_i \le 10^5)$

输入 $n$ 个数，代表每只狼的加成值 $(0\le b_i\le 5\times10^4)$

每组样例输出一个Case，然后输出答案。

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