P8102 「LCOI2022」 Cow Insertion

Farmer John 迎来了新奶牛——Bessie。每个奶牛都会有一定的开心值，Farmer John 希望 Bessie 能更幸福的生活在这里。

牛棚里原来有 $n$ 头奶牛，开心值的感染距离 $m$，并且 $a_i$ 表示原来牛棚中第 $i(1\le i\le n)$ 头牛的开心值。并且，Bessie 同样拥有一个开心值 $A$。 整个牛棚的开心值是 $\sum\limits_{i=1}^{n-m+1}\ \max\limits_{i\le j\le i+m-1}\ a_j$，Bessie 可以住在任意两头牛的中间或起始以及最后。Farmer John 想知道：Bessie 来这里之后，整个牛棚的开心值最大为多少。

无

无

【样例解释】 - 当 Bessie 在第一个位置时（$50,60,100,70$），整个牛棚的开心值的最大值为 $\newcommand{\cases}[1]{\{#1\}}\max\cases{60,50}+\max\cases{60,100}+\max\cases{100,70}$，即 $60+100+100=260$。 - 当 Bessie 在第二个位置时（$60,50,100,70$），整个牛棚的开心值的最大值为 $\newcommand{\cases}[1]{\{#1\}}\max\cases{60,50}+\max\cases{50,100}+\max\cases{100,70}$，即 $60+100+100=260$。 - 当 Bessie 在第三个位置时（$60,100,50,70$），整个牛棚的开心值的最大值为 $\newcommand{\cases}[1]{\{#1\}}\max\cases{60,100}+\max\cases{100,50}+\max\cases{50,70}$，即 $100+100+70=270$。 - 当 Bessie 在第四个位置时（$60,100,70,50$），整个牛棚的开心值的最大值为 $\newcommand{\cases}[1]{\{#1\}}\max\cases{60,100}+\max\cases{100,70}+\max\cases{70,50}$，即 $70+100+100=270$。 显然，整个牛棚的开心值的最大值为 $\newcommand{\cases}[1]{\{#1\}}\max\cases{260,260,270,270}=270$。 【数据范围与约定】 |subtask|$n\le$|分值| |:-:|:-:|:-:| |$1$|$5\times10^2$|$10$| |$2$|$5\times10^3$|$20$| |$3$|$5\times10^6$|$70$| 对于 $100\%$ 的数据，$1\le m\le n$，$0\le a_i, A\le100$。