问题 4252 --献爱心

4252: 献爱心

题目描述

  小W欢度国庆,来到武宜路发现人头攒动,这是因为大家都准备从市民广场上那个大屏幕观看新中国国庆阅兵式!这虽然是一件很喜庆的事情,可却让WJ区的警察局长伤透了脑筋,因为人潮拥挤很容易发生安全事故。
为了防止意外以及能够及时处理安全问题。他们特意将武宜路分成了N等份,每一份设置一个群众集会点,总共有N个集会点。在国庆这天每个聚集点都会聚集一定数量的群众,而同时也会有警察来管理这些集会点。因为WJ其他很多地方都需要巡逻,所以只有有限的M个警察能够被分配到了武宜路上,而他们的能力也有限,一个人只能管理连续的K个集会点。
热心的小W决定帮忙,在给出每个集会点将要聚集的群众人数,小W通过编程告诉警察最多能够管理到多少群众。
如有10个集会点,3个警察,每个警察能管理连续2个集会点。
10 5 34 4 26 12 75 15 8 20
所以最多能够管理到167个群众。

输入

第一行有三个数 N,M,K。如题所述。
接下来一行N个数,第i个数A[i]表示武宜路上集会点i的群众人数;

输出

输出共一行一个数,表示警察最多能管理的群众人数。

样例输入输出

输入#1 复制
7 4 1
2 43 32 4 64 1 10
输出#1 复制
149

提示

【数据范围】
30%的数据: 1≤N,M,K≤100; 1≤A[i]≤20;
100%的数据: 1≤N,M,K≤1,000; 1≤A[i]≤200,000;

序号 标题 作者 发表时间 费用 订购数 操作