程序设计基础一的上机考试题目已在OJ开放,大家可以补题了。

Problem 1508. -- 最优序列

1508: 最优序列

Time Limit: 1 Sec  Memory Limit: 65535 MB   64bit IO Format: %lld
Submitted: 102  Accepted: 34
[Submit][Status][Web Board]

Description

给定一个长度为N的正整数序列,求一个子序列,使得原序列中任意长度为M的子序列中被选出的元素不超过1个。要求选出的元素之和最大。

Input

有多组测试数据
每组测试数据的第一行是两个整数n和m(1≤N≤1000,1≤M≤100),第二行给出了n个正整数。

Output

每组测试数据额输出占一行,包含一个整数,表示选出的最优序列中所有整数的和。

Sample Input

10 4
1 3 1 1 1 1 1 1 3 1
10 4
7 3 4 8 2 6 5 7 4 8

Sample Output

6
21

Source

[Submit][Status][Web Board]