8705: Problem I. 小E的ToDoList

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:159 通过:6

题目描述

小E喜欢写 To Do List  , 但他却总是因为懒而完成不了, 今天他终于下定决心要“清空” To Do List 了。

小E发现他的 To Do List 中还有 $n$ 个未完成的任务,但因为能力有限, 小E只能完成 $m$ 个任务。

每完成一个任务,小E都会获得一定的幸福感。如果完成了第$i$ 个任务,小E将获得 $a_i$ 幸福感。

但小E有一个怪癖,如果任务的序号为偶数,小E将不会完成这个任务。

如果小E完成了一个任务,序号在这个任务之后的所有任务的序号都会减少一位,当然它们能获得的幸福感并不会因此改变。

请你告诉小E他最多能获得多少幸福感。

输入格式

第一行包含$2$个整数$n$,$m$,$(1\le n \le 10^6,1\le m \le n)$分别表示任务的个数和能完成任务的数量。

第二行包含$n$个整数$a_1, a_2, a_3,\dots,a_n(1\le a_i\le10^6)$ 表示$n$个任务所能获得的幸福感。

输出格式

输出一个整数,表示答案

输入样例 复制

6 2
1 1 4 5 1 4

输出样例 复制

9

数据范围与提示

样例输入2:
6 1
1 1 4 5 1 4

样例输出2:
4


对于第一个样例

初始任务序列为$[1, 1, 4, 5, 1, 4]$, 小E只能完成序号为$1、3、5$的任务$[1, 4, 1]$,小E先完成序号$3$的任务,获得 $4$ 幸福感。

此时任务序列为$[1, 1, 5, 1, 4]$, 小E继续完成序号为$3$的任务, 获得 $5$ 幸福感。

小E总共获得 $9$ 幸福感,可以证明小E不能获得更多的幸福感。