358D. D. Dima and Hares

CF358D. Dima and Hares

时限: 2 秒 | 内存: 256 MB | 输入: 标准输入 | 输出: 标准输出

Dima 非常喜欢 Inna 送给他的礼物，他甚至更喜欢 Seryozha 送给他的礼物。

Dima 非常感谢 Inna 的礼物，于是决定送她 $n$ 只野兔。Inna 十分高兴，她将这些野兔排成一行，从左到右给它们编号 $1$ 到 $n$，然后开始喂它们胡萝卜。Inna 决定每只野兔都只喂一次。但她应该按什么顺序喂它们呢？

Inna 发现，每当她喂一只野兔时，它都会表现出喜悦；而具体表现出的喜悦取决于在喂它之前，邻近的野兔是否已经被喂过。Inna 知道，如果一只野兔在它的两个相邻野兔都还饿着、或者恰好一个相邻野兔已经吃饱、或两个相邻野兔都已吃饱时，分别会表现出多少喜悦。注意，第 $1$ 只和第 $n$ 只野兔分别没有左邻、右邻，所以它们永远不可能有两个吃饱的相邻野兔。

请帮助 Inna 最大化所有野兔表现出的总喜悦值。

输入格式

输入的第一行为一个整数 $n$（$1 \leq n \leq 3000$），表示野兔的数量。接下来有三行，每行包含 $n$ 个整数。第一行为 $a_1, a_2, \dots, a_n$，第二行为 $b_1, b_2, \dots, b_n$，第三行为 $c_1, c_2, \dots, c_n$。对所有 $i$ 均有 $0 \leq a_i, b_i, c_i \leq 10^5$。

第 $i$ 个数 $a_i$ 表示当第 $i$ 只野兔两侧的邻居都还饿着时，表现出的喜悦值。$b_i$ 表示当正好有一个相邻野兔已经吃饱时，表现出的喜悦值。$c_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