选元素（数据加强版）

题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,…,a_n$。

请你从中挑选 $x$ 个元素，要求：

1. 原序列中的每一个长度为 $k$ 的连续子序列都至少包含一个被选中的元素。
2. 满足条件 $1$ 的前提下，所选 $x$ 个元素的相加之和应尽可能大。 输出最大可能和。

输入格式

第一行包含三个整数 $n,k,x$。

第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$。

输出格式

如果无法满足题目要求，则输出 $−1$。

否则，输出一个整数，表示所选元素的最大可能和。

样例输入 1

5 2 3
5 1 3 10 1

样例输出 1

18

样例输入 2

6 1 5
10 30 30 70 10 10

样例输出 2

-1

样例输入 3

4 3 1
1 100 1 1

样例输出 3

100

数据范围

所有测试点满足 $1≤k,x≤n≤2500，1≤a_i≤10^9$。