跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F1907. George and Job

  • ID: 1913
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:进阶
  • 上传者:
  • 动态规划
  • 模拟
  • 编程与模拟
  • 进阶
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

George and Job

题目描述

C. George and Job
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The new ITone 6 has been released recently and George got really keen to buy it. Unfortunately, he didn't have enough money, so George was going to work as a programmer. Now he faced the following problem at the work.

Given a sequence of n integers p1,p2,...,pn. You are to choose k pairs of integers:

[l1,r1],[l2,r2],...,[lk,rk](1≤l1≤r1<l2≤r2<...<lk≤rk≤n;ri-li+1=m),

in such a way that the value of sum is maximal possible. Help George to cope with the task.

Input

The first line contains three integers n, m and k (1≤(m×k)≤n≤5000). The second line contains n integers p1,p2,...,pn (0≤pi≤109).

Output

Print an integer in a single line − the maximum possible value of sum.

Examples
Input
5 2 1
1 2 3 4 5
Output
9
Input
7 1 3
2 10 7 18 5 33 0
Output
61

题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 1483 题。保留原作者与原赛事署名。