P5124 [USACO18DEC] Teamwork G

在 Farmer John 最喜欢的节日里，他想要给他的朋友们赠送一些礼物。由于他并不擅长包装礼物，他想要获得他的奶牛们的帮助。你可能能够想到，奶牛们本身也不是很擅长包装礼物，而 Farmer John 即将得到这一教训。 Farmer John 的 $N$ 头奶牛（$1\le N\le 10^4$）排成一行，方便起见依次编号为 $1\dots N$。奶牛 $i$ 的包装礼物的技能水平为 $s_i$。她们的技能水平可能参差不齐，所以 FJ 决定把她的奶牛们分成小组。每一组可以包含任意不超过 $K$ 头的连续的奶牛（$1\le K\le 10^3$），并且一头奶牛不能属于多于一个小组。由于奶牛们会互相学习，这一组中每一头奶牛的技能水平会变成这一组中水平最高的奶牛的技能水平。 请帮助 FJ 求出，在他合理地安排分组的情况下，可以达到的技能水平之和的最大值。

无

无

在这个例子中，最优的方案是将前三头奶牛和后三头奶牛分别分为一组，中间的奶牛单独成为一组（注意一组的奶牛数量可以小于 $K$）。这样能够有效地将 $7$ 头奶牛的技能水平提高至 $15$、$15$、$15$、$9$、$10$、$10$、$10$，和为 $84$。