新四军抓汉奸
Description:
新四军在一次战役中抓到了n个汉奸，把他们排成一排，从左到右编号为1到n，然后开始审讯他们。
每个人只能审讯一次，汉奸都是怕死鬼，所以审问一次都会说出一些情报。
但是询问顺序是有必要的，因为他们说出情报的多少是有关联的。
如果对于第i个汉奸来说，
如果他左右i-1和i+1两个汉奸都没有说出情报，则他能说出a[i]份情报。
如果他左右i-1和i+1两个汉奸有且只有一个说出了情报，则他能说出b[i]份情报。
如果他左右i-1和i+1两个汉奸都说出了情报，则他能说出c[i]份情报。
众所周知，第1个汉奸没有左边，第n个汉奸没有右边。
已知每份情报都不同，问，新四军如何决策能获得最多的情报？
Input:
输入数据有4行。
第一行一个n，表示下面有n个汉奸。(n<=1e5)
第二行n个数，a1，a2......an。(0<=a[i]<=1e9)
第三行n个数，b1，b2......bn。(0<=b[i]<=1e9)
第四行n个数，c1，c2.......cn。(0<=c[i]<=1e9)
Output:
输出一行，可获得最多情报数。
Sample Input:
7 8 5 7 6 1 8 9 2 7 9 5 4 3 1 2 3 3 4 1 1 3
Sample Output:
44
Source:
Submit