Description

给定 n 个整数和整数 k，要把序列分成 k 段连续非空区间。每段得分为该段元素和，若得分为负则按 0 计。求最大总得分。

Input Format

第一行两个整数 n 和 k。第二行 n 个整数。

Output Format

一行一个整数，表示最大总得分。

5 2
3 -5 4 2 -1

9

Hint

用前缀和快速求区间和，再进行分段 DP。