题目描述

现有 (N) 本书排成一排，第 (i) 本书的页数为 (pages_i)。现在需要将这些书分配给 (M) 位志愿者。

分配时必须满足以下要求：

1. 每位志愿者分到的书籍必须是连续的一段，不能将不连续的书籍分给同一位志愿者。
2. 每本书必须分配给且只能分配给一位志愿者。
3. 每位志愿者至少分到一本书。

每位志愿者所获得的书籍页数等于其分到的所有书籍页数之和。

请你设计一种分配方案，使得所有志愿者中，获得书籍页数最多的那位志愿者的总页数尽可能小，并输出这个最小值。

输入格式

第一行包含两个整数 (N) 和 (M)，分别表示书籍的数量和志愿者的人数。

第二行包含 (N) 个整数 (pages_1,pages_2,\ldots,pages_N)，表示每本书的页数。

输出格式

输出一个整数，表示在满足所有分配要求的前提下，所有志愿者获得的书籍页数最大值的最小值。

样例输入

4 2
12 34 67 90

样例输出

113

数据范围

• 对于 30% 的数据，(1\le N\le 20)，(1\le M\le 10)。
• 对于 60% 的数据，(1\le N\le 500)，(1\le M\le 50)。
• 对于 100% 的数据，(1\le N\le 10^5)，(1\le M\le 1000)。
• (1\le pages_i\le 10^9)。

保证 (1\le M\le N)。