P2545 [AHOI2004] 实验基地
题目描述
经过不懈努力，我国科学家将正式启动 Samuel 星球研究计划。目前阶段的任务是采用飞船将智能机器人运送到该星球以建立临时实验基地进行深入的科学探索实验。为了激发广大学生的科学兴趣，科学家们还在全球范围内设立学生研究组（简称 SRT）。经过层层选拔，小可可终于入选该研究组。
科学家前辈们交给小可可一项简单的运筹任务：
在前期的绕 Samuel 星球探测计划中，发现该星球有若干处狭长的平坦地带可以用于登陆（亦称为“登陆地带”）。科学家们计划在登陆地带上建立实验基地。但是，并不是任何登陆地带都适宜建立实验基地。
为此，科学家们已将每一个登陆地带都划分成 $2 \times N$ 个矩形。不同的登陆地带其 $N$ 值不同。在绕 Samuel 星球探测计划中，已经对各个矩形土地的适用度做了评估。例如，某 $2 \times 9$ 登陆地带的适用度评估值如下表所示：
在这些矩形土地中，适用度为正数的，其土地比较结实平坦，适合建立实验基地，正值越高，就越安全，越适合建立基地。有些矩形土地适用度为负数，这表明该片土地有危险性，负得越多，就越不适合建立实验基地。
科学家希望从登陆地带中自行选取一段 $2 \times Q$ 的区域建立实验基地。不过为了研究方便，规定在 $2 \times Q$ 区域中的第一行选一段长度为 $P$ 的区域空出来，作为采集样品的场所——此场所将不算作实验基地。这样一来，实验基地的形状看上去就是一个“凹”字型。
例如，下图就是一个选取方案。粗线条框内的区域就是实验基地，它开辟出了一个 $2\times5$ 的区域，并且在第一行中选出了长度为 $2$ 的样品采集区，样品采集区的适用度分别为 $-4$ 和 $-5$。
注意：$Q$ 和 $P$ 在 $N$ 的范围内可以自行任意选取，但是必须要设置样品采集区，而且样品采集区的左右两侧必须存在实验基地。故以下形状的实验基地是不允许出现的：
科学家们将实验基地所占据的各个矩形土地其适用度之和称为该实验基地区，而且样品采集区的左右两侧必须存在实验基地。故以下形状的实验基地是不允许出现的：
科学家们将实验基地所占据的各个矩形土地其适用度之和称为该实验基地的适用度。科学家们希望所建立的实验基地适用度能够尽可能大，并把这个实验基地的选址任务交给了小可可。现在请你为小可可编写程序进行选址。
输入格式
第一行有一个整数 $N(3 < N < 2000)$，表示登陆地带的大小是 $2 \times N$。随后的两行每一行有 $N$ 个整数（其绝对值不超过 $10^6$），表示对应的矩形土地的适用度评估值，各个整数之间用一个空格隔开。
输出格式
只有一行输出，为整数 $M$，即所确定的实验基地的适用度。
说明/提示
数据范围见输入格式。