题目描述

给定n个整数组成的序列，现在要求将序列分割为m段，每段子序列中的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达到最小？

输入格式

第一行 给定一个整数n和一个整数m,分别表示序列的长度为n,将其分为m段。(1 第二行 输入n个整数x，表示序列对应位置的值()

输出格式

输出满足序列分为m段子序列的和的最大值的最小值

9 3
9 8 7 6 5 4 3 2 1

17

提示

对于样例，我们可以分别{9,8}和{7,6}和{5,4,3,2,1},他们当中最大值为17