4005: 【NOIP2022赛前集训】踏步向前(walk)
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：15
解决：2
题目描述
walk.in/out/cpp
你在玩一个古老的游戏。
给定一个 $2\times n$ 的格子，最初你站在第一列，即你的左脚和右脚分别在第一行和第二行的第一列。
之后每一步，你可以选择一只脚向前移动若干格，即从第 $x$ 行第 $i$ 列移动到第 $x$ 行第 $j$ 列，要求 $i < j \le n$。并将第 $x$ 行第 $j$ 列的格子上的权值累加到答案中。注意权值可能为**负数**。
并且由于腿长限制，任意时刻两只脚相隔的列不能超过 $k$。形式化的，假定左脚在第 $i$ 列，右脚在第 $j$ 列，则任意时刻需要满足 $|i-j|\le k$。
问最后两只脚都移动到第 $n$ 列，答案的最大值。
**注意：**第一列格子的权值也要累加到答案中。
输入
第一行两个正整数 $n,k$，分别表示两个序列的长度，以及两脚任意时刻距离限制。
第二行 $n$ 个整数，表示 $a_1,a_2,\cdots ,a_n$，表示第一行格子的权值。
第三行 $n$ 个整数，表示 $b_1,b_2,\cdots ,b_n$，表示第二行格子的权值。
第二行 $n$ 个整数，表示 $a_1,a_2,\cdots ,a_n$，表示第一行格子的权值。
第三行 $n$ 个整数，表示 $b_1,b_2,\cdots ,b_n$，表示第二行格子的权值。
输出
一行一个整数表示最大权值。
样例输入 复制
4 1
0 2 2 8
0 -10 5 2样例输出 复制
19提示
样例输入 2
7 20 -10 -6 2 -10 0 0
5 3 -2 -1 -10 -10 0
样例输出 2
9
数据范围及提示
对于所有数据，满足 $k\leq n\leq 10^5,|a_i|,|b_i|\leq 10^4$。
- subtask1（$10\text{pts}$）：满足 $n\leq 300$。
- subtask2（$20\text{pts}$）：满足 $a_i,b_i$ 均为 $0$ 或 $-1$。
- subtask3（$20\text{pts}$）：满足 $n\leq 3000$。
- subtask4（$50\text{pts}$）：无特殊限制。