【POJ Challenge】生日礼物

给定一个长度为 $N$ 的整数序列 $A_1,A_2,\ldots,A_N$。在序列中选择不超过 $M$ 个连续子段作为生日礼物，求所选元素之和的最大值。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示序列长度和最多可以选择的连续子段数。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$，表示给定的整数序列。

输出格式

输出一个整数，表示所选元素之和的最大值。

样例输入

5 2
2 -3 2 -1 2

样例输出

5

数据范围

• $1\le N\le 10^5$；
• $0\le M\le 10^5$；
• $0\le |A_i|\le 10^4$。

来源与许可

本题为 POJ Challenge 试题「生日礼物」，题面与测试数据整理自 BZOJ 2288。

样例 1

输入

5 2
2 -3 2 -1 2

输出

5