Layoff Mastery

ZZY has a unique way to perform layoffs. There are n students with exam scores a_i (\(-1000 \le a_i \le 1000\)). ZZY wants to keep some of them by selecting at most k contiguous segments from the list. The objective is to maximize the sum of the scores of the kept students. Note that a wrong answer in the exam causes a score penalty, so scores can be negative. It is allowed to keep no student (i.e. select no segment) in order to avoid a negative total score.

Problem Formulation:

Given an integer n (\(1 \le n \le 500\)) and an integer k (\(1 \le k \le n\)), along with an array \(a = [a_1, a_2, \dots, a_n]\), select at most \(k\) non-overlapping contiguous segments such that the sum of all elements in these segments is maximized. If no segment is selected, the total is considered to be 0.

Dynamic Programming Hint:

You may use a DP formulation where dp[i][j] represents the maximum sum achievable from the first i elements using exactly j segments while not currently in an ongoing segment, and a helper state (say, best[i][j]) to handle segments currently in progress.

All formulas and notation in this problem are written in LaTeX format.

inputFormat

The first line contains two integers \(n\) and \(k\). The second line contains \(n\) integers representing the scores \(a_1, a_2, \dots, a_n\).

Constraints: \(1 \le n \le 500\), \(1 \le k \le n\), and \(-1000 \le a_i \le 1000\).

outputFormat

Output a single integer: the maximum sum of scores obtainable by selecting at most \(k\) non-overlapping contiguous segments.

Note: Selecting no segment is allowed, which yields a sum of 0.

sample

5 2
1 2 -1 3 1

7