Background

The neighboring new Grade 7 computer class just finished an exam, and it is BlingBling’s downsizing time again. The teacher assigned this task to ZZY, but since ZZY is busy solving problems, he passed this important task onto you.

Problem Description

ZZY has a unique downsizing method: each student has an exam score $a_i$ ($-1000 \le a_i \le 1000$). Among $n$ students ($n \le 500$), choose no more than $k$ ($k \le n$) contiguous segments of students to keep, and dismiss the unselected students, so that the sum of the remaining students’ scores is maximized. Note that wrong answers deduct points [don’t ask me why], so scores may be negative.

Input Format

The first line contains $n, k$. The second line contains the scores of students $1$ to $n$.

Output Format

A single number $s$, the maximum sum of scores.

5 3
1 -1 1 -1 1

3

Hint

2014 Peng Kunzhi: "The statement is so short — looks trivial at first glance."

Translated by ChatGPT 5