给定一个长度为 $n$ 的整数序列 $a_1,a_2,…,a_n$。
请你从中挑选 $x$ 个元素,要求:
- 原序列中的每一个长度为 $k$ 的连续子序列都至少包含一个被选中的元素。
- 满足条件 $1$ 的前提下,所选 $x$ 个元素的相加之和应尽可能大。 输出最大可能和。
输入格式
第一行包含三个整数 $n,k,x$。
第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$。
输出格式
如果无法满足题目要求,则输出 $−1$。
否则,输出一个整数,表示所选元素的最大可能和。
数据范围
所有测试点满足 $1≤k,x≤n≤2500,1≤a_i≤10^9$。
输入样例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