← 返回题目列表

Codeforces · 358/D

D. 迪玛和野兔

中文机器翻译题面 查看原题

迪玛非常喜欢伊娜送的礼物。他更喜欢谢廖扎送的礼物。

迪马对伊娜的礼物非常感激,决定给她买兔子。伊娜非常高兴。她把兔子排成一排,从左到右从1到n编号,然后开始给它们喂胡萝卜。伊娜决定只给每只兔子喂一次。但她应该按什么顺序喂它们呢?

Inna 注意到,当她喂兔子时,每只兔子都会散发出快乐。而特定野兔的快乐程度取决于因娜在喂它之前是否喂过它的相邻野兔。伊娜知道,当一只兔子在两只相邻的兔子都饿了,或者其中一只相邻的兔子吃饱了(即已经吃饱了),或者两只相邻的兔子都吃饱时,它会散发出多少快乐。请注意,1 号和 n 号野兔没有对应的左相邻野兔和右相邻野兔,因此它们永远不可能有两只完全相邻的野兔。

帮助 Inna 最大限度地提高兔子散发出的快乐。 :)

输入

输入的第一行包含整数 n (1 ≤ n ≤ 3000) — 野兔的数量。接下来是三行,每行有n个整数。第一行包含整数 a1 a2 ... an。第二行包含 b1, b2, ..., bn。第三行包含c1,c2,...,cn。满足以下限制:0 ≤ ai、bi、ci ≤ 105。

第一行中的数字 ai 表示如果相邻的兔子都饿了,编号 i 的兔子会感到多么高兴。第二行中的数字 bi 表示,如果编号 i 的兔子刚好有一只完整的相邻兔子,那么它会散发出喜悦。第三行中的数字 сi 表示当相邻的两只兔子都吃饱时,编号为 i 的兔子所散发出的喜悦。

输出

在一行中,打印 Inna 通过喂养野兔可以获得的最大可能的总快乐。

示例

输入 #1

4
1 2 3 4
4 3 2 1
0 1 1 0

输出 #1

13

输入 #2

7
8 5 7 6 1 8 9
2 7 9 5 4 3 1
2 3 3 4 1 1 3

输出 #2

44

输入 #3

3
1 1 1
1 2 1
1 1 1

输出 #3

4