Description

n个数字，求不相交的总和最大的最多k个连续子序列。 1<= k<= N<= 1000000。

Format

Input

Output

Samples

5 2
7 -3 4 -9 5

13

Limitation