数组覆盖

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

给定长度为 $n$ 的整数数组。请选择恰好 $k$ 个互不相同的连续子数组，使原数组的每个位置至少属于一个被选子数组，并最大化这些子数组元素和的总和。

输入格式

第一行两个整数 $n,k$。第二行 $n$ 个整数 $a_i$。

输出格式

输出能够得到的最大总和。

样例输入 1

5 4
6 -4 -10 -4 7

样例输出 1

11

数据范围

对于全部数据，$1\le n\le100000$，$1\le k\le n(n+1)/2$，$-50000\le a_i\le50000$。

题目来源：Codeforces 720F。