题目描述

小雷驾驶着飞船登陆了开普勒-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（1≤M≤N≤10 的 $5$ 次方），分别表示岩石样本的数量和样本储存筒的数量，整数间以一个 空格隔开；

输出格式

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

5 3
5 20 15 13 13

27