小猫照片 - 代码源竞赛平台

题目描述

蜗蜗有 $n$ 张按顺序排列的小猫照片，第 $i$ 张照片的价值为 $a_i$。

蜗蜗需要从中恰好选择 $x$ 张照片，并满足以下要求：对于原序列中任意一段长度不小于 $k$ 的连续区间，都至少选择其中的一张照片。

请你求出所选照片的价值之和最大可以是多少。如果不存在满足要求的选择方案，则输出 $-1$。

输入格式

第一行包含三个整数 $n,k,x$，分别表示照片数量、连续区间的长度限制，以及需要选择的照片数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每张照片的价值。

输出格式

输出一行一个整数，表示所选照片价值之和的最大值。如果不存在满足要求的选择方案，输出 $-1$。

样例

4 2 2
1 7 3 4

11

样例解释

选择第 $2$ 张和第 $4$ 张照片，价值之和为 $7+4=11$。

原序列中每一段长度不小于 $2$ 的连续区间都包含这两张照片中的至少一张，因此这个方案满足要求。

数据范围

对于 100% 的数据，保证 $1\le n\le 5000$，$1\le k,x\le n$，$1\le a_i\le 10^9$。