题目描述

小Y人美心善，为了让你更快地解决问题，已经确定了书柜的行数，其中每行的高度都是1，现在他想让你确认书柜的宽度。

由于小Y有独特的癖好，他摆书时一定是按列一列一列摆放（但每一列不一定需要摆满），且他每本书都有一个编号，他必须按照这个编号依次摆书。

举个例子，以下方案是可以的：

但是以下方案是不可行的：

因为第三本书摆在了第二本书的前面。

现在我们记每一列的宽度为这一列中最宽的书的宽度。

书柜的宽度=Σ每一列的宽度+列数-1（因为你每一列中间还要留一个宽度的空，不然多丑陋啊）

现在，请你求最小的书柜宽度为多少。

输入格式

第一行两个数字，n，h，分别表示书本的数量和书柜的行数。 接下来n行，每行一个数字，表示第i本书的宽度，wi。

输出格式

输出一行，即书柜的最小宽度。

9 3
9
7
9
4
5
11
9
10
2

30

6 4
3
2
5
3
5
5

9

5 2
4
5
2
4
5

14

说明/提示

样例解释： 对于第3个样例，我们按照这样的摆放模式，能够得到最小值。

对于20%的数据，我们保证$n \le 10$。

对于40%的数据，我们保证$n \le 50$。

对于100%的数据，我们保证$n \le 5000，h \le 5000，w_i \le 1e5$。