310003 - k个最大连续子序列和

在一个长度为N的数列中,求k个连续子序列,使得这k个连续子序列的和最大,且k个子序列无公共元素。

即给定由n个整数(可能为负整数)组成的序列a_1,a_2,…,a_n(-100≤a_i≤100),以及一个正整数k,要求确定序列a_1,a_2,…,a_nk个不相交的子段,使这k个子段的总和达到最大。

Input

第一行:n,k(1≤n≤1000,2≤k≤10)

第二行:a_1,a_2,… a_n,每个数中间以空格分隔。

Output

k个子段的最大和。

Examples

Input

10 2
-1 1 -2 3 4 -2 -5 5 6 7

Output

25
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题