题目描述

给定一个长度为n的整型序列，求$m$个不相交的子段，使得子段的和最大。

输入格式

第一行两个正整数 $n$ 和 $m$ 。 第二行$n$个整数，表示输入的整型序列。

输出格式

一行一个整数，表示最大的m段子段和。

样例1

输入

5 2
3 -7 2 -1 4

输出

8

数据规模与约定

对于 $20\%$ 的数据，$2\le m \le n \le 50$。 对于 $50\%$ 的数据，$2\le m \le n \le 500$。 对于 $20\%$ 的数据，$2\le m \le n \le 5000$。