You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小雷驾驶着飞船登陆了开普勒-22b星球，他采集了 $N$ 块直径相同的圆柱体岩石样本，编号为 $1$ 到 $N$。飞船上有 $M$ 个从左到右整齐排列的样本储存筒，其直径与岩石样本相同，且储存筒的高度可任意调节（如果某个储存筒的高度发生变化，其余储存筒也变为相同的高度），使每个岩石样本都能够完整存入储存筒中。现要将 $N$ 块岩石样本按照编号从小到大依次放入储存筒，存放规则如下：

1）1 号岩石样本必须放在左边第一个储存筒中； 2）$i$ 号$（2≤i≤N）$岩石样本可以选择叠放在 $i-1$ 号岩石样本所在的储存筒中，但是必须使用厚度为 $1$ 的保护垫将两块岩石样本隔开；也可以放在左侧第一个空的储存筒中。请问按照上述规则存放岩石样本，如何才能使储存筒的高度最小？

请计算这个最小高度。例如：$N = 5，M = 3，$1 到 5 号岩石样本的高度依次为 5，20，15，13，13，按照下图所示存入岩石样本可使得储存筒的高度最小，为 27。

输入

第一行输入两个整数 $N、M$，分别表示岩石样本的数量和样本储存筒的数量，整数间以一个空格隔开；

第二行输入 $N$ 个整数 $P_i$，表示第 $i$ 号岩石样本的高度，整数间以一个空格隔开。

输出

输出一个整数，表示样本储存筒的最小高度。

5 3
5 20 15 13 13

27