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