CF1077F2.Pictures with Kittens (hard version)

The only difference between easy and hard versions is the constraints.

Vova likes pictures with kittens. The news feed in the social network he uses can be represented as an array of $n$ consecutive pictures (with kittens, of course). Vova likes all these pictures, but some are more beautiful than the others: the $i$-th picture has beauty $a_i$.

Vova wants to repost exactly $x$ pictures in such a way that:

• each segment of the news feed of at least $k$ consecutive pictures has at least one picture reposted by Vova;
• the sum of beauty values of reposted pictures is maximum possible.

For example, if $k=1$ then Vova has to repost all the pictures in the news feed. If $k=2$ then Vova can skip some pictures, but between every pair of consecutive pictures Vova has to repost at least one of them.

Your task is to calculate the maximum possible sum of values of reposted pictures if Vova follows conditions described above, or say that there is no way to satisfy all conditions.

简单版本与困难版本的唯一区别在于约束条件。

沃瓦喜欢有小猫的图片。他所使用的社交网络中的信息流可以表示为一个由 $n$ 张连续图片（当然都是小猫图片）组成的数组。沃瓦喜欢所有这些图片，但其中一些比另一些更美：第 $i$ 张图片的美感值为 $a_i$。

沃瓦希望恰好转发 $x$ 张图片，且满足以下条件：

• 信息流中任意长度至少为 $k$ 的连续图片段中，都至少有一张图片被沃瓦转发；
• 被转发图片的美感值之和尽可能大。

例如，若 $k=1$，则沃瓦必须转发信息流中的所有图片；若 $k=2$，则沃瓦可以跳过某些图片，但在每一对相邻图片之间，沃瓦必须至少转发其中一张。

你的任务是：在满足上述所有条件的前提下，计算被转发图片的美感值之和的最大可能值；若无法满足所有条件，则说明不存在可行方案。

The first line of the input contains three integers $n, k$ and $x$ ($1 \le k, x \le n \le 5000$) — the number of pictures in the news feed, the minimum length of segment with at least one repost in it and the number of pictures Vova is ready to repost.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the beauty of the $i$-th picture.

输入的第一行包含三个整数 $n, k$ 和 $x$（$1 \le k, x \le n \le 5000$）—— 分别表示新闻动态中图片的数量、要求至少包含一张转发的区间的最小长度，以及 Vova 准备转发的图片数量。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），其中 $a_i$ 表示第 $i$ 张图片的美观度。

Print -1 if there is no way to repost some pictures to satisfy all the conditions in the problem statement.

Otherwise print one integer — the maximum sum of values of reposted pictures if Vova follows conditions described in the problem statement.

如果无法通过转发某些图片来满足题目描述中的所有条件，则输出 $-1$。

否则，输出一个整数——在伏拉满足题目描述的条件下，被转发图片的价值之和的最大值。