1184: 拆球场
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：49
Solved：13
Description
狂热足球迷 Ken 又想为中国足球出份力啦。
他买下了从左到右排列的连续 $n$ 块足球场，每块足球场都分为上下两部分均等的正方形。
最初他找来了顶级设计师为每块足球场都做了定制设计。
由于 Ken 名声大噪，吸引了众多足球爱好来踢球。
通常两支球队都会进行五人制比赛，因此只需要占据一块足球场的某一部分。
根据草皮质量、场边装修的不同，每一块球场的上下部分都得到了平时来踢球的球迷的不同评分，而这些评分也变成了评估球场的价值。
有一天，可恶的政府找上门来，要求 Ken 拆除这些球场，因为这些球场占据了城市大片土地面积。
他们还添加了一个理由：中国足球太烂了，建这么多球场太浪费资源了······
无奈，根据要求 Ken 必须一个月拆除一块足球场，且只保留原先最左边的球场。
政府也给出了相应的赔偿规则：某个月拆除了球场 $A$，球场 $A$ 上半部分和下半部分的价值分别记为：$a1、a2$，球场 $A$ 左边第一个未拆除的球场 $B$ 的上半部分和下半部分的价值分别记为：$b1、b2$，则相对应的赔偿为：$(b1+a1)+ (|b2-a2|)$。拆除了 $A$ 之后，其上半部分和下半部分的价值分别会累加至 $B$ 的上半部分和下半部分。
请你帮帮 Ken 想想办法，如何拆除才能获得最高赔偿？
他买下了从左到右排列的连续 $n$ 块足球场，每块足球场都分为上下两部分均等的正方形。
最初他找来了顶级设计师为每块足球场都做了定制设计。
由于 Ken 名声大噪，吸引了众多足球爱好来踢球。
通常两支球队都会进行五人制比赛，因此只需要占据一块足球场的某一部分。
根据草皮质量、场边装修的不同，每一块球场的上下部分都得到了平时来踢球的球迷的不同评分，而这些评分也变成了评估球场的价值。
有一天，可恶的政府找上门来，要求 Ken 拆除这些球场，因为这些球场占据了城市大片土地面积。
他们还添加了一个理由：中国足球太烂了，建这么多球场太浪费资源了······
无奈，根据要求 Ken 必须一个月拆除一块足球场，且只保留原先最左边的球场。
政府也给出了相应的赔偿规则：某个月拆除了球场 $A$，球场 $A$ 上半部分和下半部分的价值分别记为：$a1、a2$，球场 $A$ 左边第一个未拆除的球场 $B$ 的上半部分和下半部分的价值分别记为：$b1、b2$，则相对应的赔偿为：$(b1+a1)+ (|b2-a2|)$。拆除了 $A$ 之后，其上半部分和下半部分的价值分别会累加至 $B$ 的上半部分和下半部分。
请你帮帮 Ken 想想办法，如何拆除才能获得最高赔偿？
Input
共 $3$ 行。
第一行，包含一个正整数 $n$，表示球场数量。
第二行，包含 $n$ 个整数，中间以空格隔开，表示从左到右的 $n$ 块足球场的上半部分价值。
第三行，包含 $n$ 个整数，中间以空格隔开，表示从左到右的 $n$ 块足球场的下半部分价值。
第一行，包含一个正整数 $n$，表示球场数量。
第二行，包含 $n$ 个整数，中间以空格隔开，表示从左到右的 $n$ 块足球场的上半部分价值。
第三行，包含 $n$ 个整数，中间以空格隔开，表示从左到右的 $n$ 块足球场的下半部分价值。
Output
输出最高赔偿。
Sample Input Copy
3
1 1 1
2 2 2Sample Output Copy
7HINT
样例解释：
总共两种拆除方式：
- 第 $1$ 个月拆了第 $2$ 块球场，赔偿：$(1+1)+(|2-2|) = 2$，第 $1$ 块球场价值变为 $(2,4)$。
第 $2$ 个月拆了第 $3$ 块球场，赔偿：$(2+1)+(|4-2|) = 5$，总赔偿为 $7$。
- 第 $1$ 个月拆了第 $3$ 块球场，赔偿：$(1+1)+(|2-2|) = 2$，第 $2$ 块球场价值变为 $(2,4)$。
第 $2$ 个月拆了第 $2$ 块球场，赔偿：$(1+2)+(|2-4|) = 5$，总赔偿为 $7$。
数据范围：
对于 $100\%$ 测试点，$3 \le n\le 12$，任意一块球场的任意部分的价值不超过 $1000$。
总共两种拆除方式：
- 第 $1$ 个月拆了第 $2$ 块球场，赔偿：$(1+1)+(|2-2|) = 2$，第 $1$ 块球场价值变为 $(2,4)$。
第 $2$ 个月拆了第 $3$ 块球场，赔偿：$(2+1)+(|4-2|) = 5$，总赔偿为 $7$。
- 第 $1$ 个月拆了第 $3$ 块球场，赔偿：$(1+1)+(|2-2|) = 2$，第 $2$ 块球场价值变为 $(2,4)$。
第 $2$ 个月拆了第 $2$ 块球场，赔偿：$(1+2)+(|2-4|) = 5$，总赔偿为 $7$。
对于 $100\%$ 测试点，$3 \le n\le 12$，任意一块球场的任意部分的价值不超过 $1000$。