CF358D Dima and Hares

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 喂食野兔能够获得的最大总喜悦值。

由 ChatGPT 5 翻译