Description

现有 N 本书排成一排，每本书的页数为 pages[i]。需要将这些书分配给M 位志愿者，每位志愿者分配到的是连续的一段书籍，且每人都至少要分配到一本书籍。 请你帮助小明找出一种分配方案，使得 所有志愿者中分到的书籍页数最少的人的最大页数值，并输出这个最少的人的最大页数值。

Format

Input

第一行包含两个整数 N 和 M，分别表示书籍的数量和志愿者的人数。 第二行包含 N 个整数，表示每本书的页数pages[i]。

Output

输出一个整数，表示在所有可能的分配方案中，志愿者获取到书籍最小的最大页数值。

Samples

4 2
12 34 67 90

90

Limitation

对于 30% 的数据：1≤≤N≤20，1≤M≤10 对于 60% 的数据：1≤N≤500，1≤≤M≤50 对于 100% 的数据：1≤N≤1e5，1≤M≤1000 1≤pages[i]≤1e9