### 问题描述 基德，一位在七大洲闻名的冒险家，他的探险生涯已经持续了 $N$ 年。在这些年份中，每一年都可以用一个整数 $A_i$ 来描述，这个数字代表了那一年的冒险收获。如果某一年的冒险收获丰富，那么 $A_i$ 会是一个正数；相反，如果那一年的冒险遭遇了困境，那么 $A_i$ 可能就会是一个负数。 每段探险历程可以用两个整数 $S$ 和 $F$ 描述，它们分别代表这段历程的开始和结束。当然，对于我们在这个问题中考虑的每一段历程，$S$ 都不会大于 $F$。 基德现在想要在他的冒险旅程中挑选两段历程，作为他最为引以为豪的探险经历，但是有一些规则需要遵守： 1. 两段历程不能有公共的年份。例如，历程 $[1, 5]$ 和历程 $[6, 7]$ 并无公共的年份； 2. 第一段历程应该早于第二段历程。例如，历程 $[1, 5]$ 早于历程 $[6, 7]$； 3. 两段历程不能太接近。在第一段历程结束和第二段历程开始之间，至少应该间隔 $K$ 年。例如，如果 $K$ 等于 $4$，那么我们可以选择历程 $[1, 5] $和历程 $[10, 10]$，但如果 $K$ 等于 $5$，那么就不能选择这两段历程了。 4. 在遵循以上规则的前提下，所选择的两段历程中的冒险收获总和应该尽可能大。 你的任务就是帮助基德选择这两段历程，并将这两段历程的冒险收获总和告诉他。 ### 输入格式 第一行输入两个整数 $N$ 和 $K$，分别表示基德的探险生涯持续了多少年，以及两段历程之间至少应该间隔多少年。 然后一行包含 $N$ 个空格分隔的整数 $A_1, A_2, ..., A_N$，表示每一年的冒险收获。 数据范围保证：$2 \leq N \leq 10^5$，$0 \leq K \leq 10^5$，$-10^9 \leq A_i \leq 10^9$，$K + 2 \leq N$。 ### 输出格式 输出一行，包含一个整数，表示所选择的两段历程的冒险收获总和。 ### 样例输入 ``` 6 0 5 -1 5 0 -1 9 ``` ### 样例输出 ``` 18 ``` ### 说明 对于测试数据，$N = 6$，$K = 0$，$A=\lbrace 5, -1, 5, 0, -1, 9 \rbrace$。最优的选择是选取第 $1、2、3$ 年和第 $6$ 年作为两段历程。但是这并不是唯一的最优选择。