CF1077F2 Pictures with Kittens (hard version)

简单版和困难版的唯一区别在于约束条件。 Vova 喜欢带有小猫的图片。他所使用的社交网络的新闻推送可以表示为一个长度为 $n$ 的连续图片数组（当然，每张图片都有小猫）。Vova 喜欢所有这些图片，但有些图片比其他的更美丽：第 $i$ 张图片的美丽值为 $a_i$。 Vova 想要转发恰好 $x$ 张图片，要求满足： - 新闻推送中每一段长度至少为 $k$ 的连续图片中，至少有一张被 Vova 转发； - 被转发图片的美丽值之和尽可能大。 例如，如果 $k=1$，那么 Vova 必须转发新闻推送中的所有图片。如果 $k=2$，那么 Vova 可以跳过一些图片，但对于每一对相邻的图片，Vova 必须至少转发其中一张。 你的任务是计算在满足上述条件的情况下，Vova 能够转发的图片美丽值之和的最大值。如果无法满足所有条件，则输出无解。

输入的第一行包含三个整数 $n, k, x$（$1 \leq k, x \leq n \leq 5000$）——新闻推送中的图片数量、每段至少要有一张被转发的最小连续图片段长度，以及 Vova 准备转发的图片数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），其中 $a_i$ 表示第 $i$ 张图片的美丽值。

如果不存在满足条件的转发方式，输出 $-1$。 否则，输出一个整数，表示在满足题目条件下，Vova 能够转发的图片美丽值之和的最大值。

由 ChatGPT 4.1 翻译