题目描述

在上语文课时，不安分的水晶经常因为无聊去打扰正在认真听课的你，你现在已经被他搞得不耐烦了。

这时，你的目光扫到了作文纸，你突发奇想，通过作文纸设计了一个游戏，心想这下应该能支开水晶了。

将作文纸上的格子看成一个长度为 $n$ 的数组，你必须将数组中的每一个单元格都涂成红色或者蓝色。

如果把第 $i$ 个单元格涂成红色，那么你会获得 $a_i$ 分数；如果把它涂成蓝色，那么你会获得 $b_i$ 分数；

对于第 $i$ 个单元格来说，每有一个与它颜色相同的相邻单元格，那么就会额外获得一次 $c_i$ 分数。

$\textbf{因为每一个单元格最多有两个相邻单元格，所以它最多获得两次额外分数。}$

请你设计一种涂颜色的方法，使得最终每个单元格的得分和最大。

输入格式

第一行输入一个 $n$ $(2 \leq n \leq 1000)$ ，代表数组的大小。

第二行输入 $n$ 个整数 $a_1,a_2,a_3,...,a_n$ $(1 \leq a_i \leq 5000)$ 代表每个单元格被涂成红色的得分。

第三行输入 $n$ 个整数 $b_1,b_2,b_3,...,b_n$ $(1 \leq b_i \leq 5000)$ 代表每个单元格被涂成蓝色的得分。

第四行输入 $n$ 个整数 $c_1,c_2,c_3,...,c_n$ $(1 \leq c_i \leq 5000)$ 代表每个单元格每有一个与它颜色相同的相邻单元格时的额外得分。

输出格式

输出一行一个整数，代表能够获得的最大分数和。

样例

3
10 1 10
1 20 1
10 1 10

44

样例解释

对于给定样例，把单元格都涂成蓝色能使得分和最大。