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