Problem5838--战狼

5838: 战狼

Time Limit: 1.000 Sec  Memory Limit: 256 MB
Submit: 28  Solved: 14
[Submit] [Status] [Web Board] [Creator:]

Description

吴京有一部著名电影叫做《战狼》,但是本题和电影没有什么关系。
你要解决的是一个战狼游戏,游戏是这样的:
在你面前有n匹狼,每匹狼有对应的攻击力a[i],并且它们还各自有一个加成攻击力b[i]。
每匹狼的实际攻击力为自身攻击力a[i],加上它相邻的两匹狼的加成攻击力。
你现在想要消灭所有的狼,你希望受到的伤害总和可以最小。



Input

第一行输入n,表示狼的数量。
第二行输入n个数a[i]表示第i匹狼的初始攻击力
第三行输入n个数b[i]表示第i匹狼的加成攻击力

Output

输出一个数表示消灭所有狼所受到的最小伤害总和

Sample Input

3
3 5 7
8 2 0

Sample Output

17

HINT

样例解释

有三头狼,刚开始第二头狼给他左右两边的狼各加2攻击力,由于第一头狼左边没有狼,所以只给第二头狼加,第三头狼还那样,一系列操作后攻击力为(5,13,9),从左往右杀死狼

1、受到5点攻击,且第二头狼的攻击力加成消失(5,9)

2、受到5点攻击,且第三头狼攻击加成消失(7)

3最后结果5+5+7=17
数据范围
n<=200,a[i]<=100000,b[i]<=50000


Source/Category

 

[Submit] [Status]