Background

PA 2012 R5.

Problem Description

Given a sequence containing $n$ numbers, find the maximum possible sum of at most $k$ non-overlapping subarrays.

Input Format

The first line contains two positive integers $n, k$.

The next line contains $n$ integers, which form the sequence.

Output Format

Output one integer, the answer.

5 2
7 -3 4 -9 5

13

Hint

For $100\%$ of the testdata, $1 \le k \le n \le 10^6$. All numbers in the sequence are within $[-10^9, 10^9]$.

Translated by ChatGPT 5