题目描述

小码哥有一个长度为$n$的序列$a_i$，他要将其划分为$m$段子区间，我们将一个子区间$[L,R]$内$i\in[L,R],a_i$的和称为这个子区间的子段和，小码哥希望划分之后，最大的子段和最小。你能告诉他这个最大的子段和是多少吗？

输入格式

第一行输入两个整数$n,m$。 第二行输入$n$个整数$a_i$。

输出格式

输出一行一个整数，表示你的答案。

样例输入 #1

5 2
1 3 2 5 4

样例输出 #1

9

说明/提示

数据范围： 对于20%的数据，有$1\leq n,m\leq 10$。 对于100%的数据，有$1\leq n,m,a_i\leq 10^5$。