集训（train）

• 题目 PID：NC26JD
• 时间限制：1 秒
• 内存限制：512 MiB

问题背景

小 S 获得了本次比赛一等奖，并得到了参加全省比赛的资格。但他发现自己的实力在省内还不够强，于是打算参加一项魔鬼集训。

问题描述

集训共安排 $n$ 天，每天的主题不同且预先固定好，例如 DFS、MST、BIT、FFT、LCT、PAM 等等。你可以挑选其中一部分日子进行集训。小 S 对某些算法比较熟悉，而对另一些算法知之甚少，所以参加各天集训获得的收益也不同。小 S 预估了一下，如果参加第 $i$ 天集训，将获得 $a_i$ 单位的能力提升。

不过强度太高的训练会有损小 S 的健康（和心态），并且他也需要一些间歇时间来消化总结错题。所以他不能连续参加超过 $k$ 天集训，否则会劳累过度 and/or 精神崩溃。求在符合此约束前提下，参加集训所能提高的能力总和最大值。

输入格式

从文件 train.in 中读取数据。

第 1 行两个正整数 $n,k$。

第 2 行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出到文件 train.out。

一个整数表示答案。

文件读写示例

freopen("train.in", "r", stdin);
freopen("train.out", "w", stdout);

样例 1

5 2
1 2 3 4 5

12

样例 1 说明

第 3 天不参加，其他 4 天都参加，可获得 $1+2+4+5=12$ 的能力提升。

数据规模与约定

• 对于 $10\%$ 的数据，$n\leq10$。
• 对于 $50\%$ 的数据，$n\leq2000$。
• 对于 $100\%$ 的数据，$1\leq k\leq n\leq100000$，$0\leq a_i\leq10^9$，保证 $a_i$ 都是在取值范围内随机生成。