406335: GYM102365 E Exciting Acts

Aram has decided to make an autobiographical play about his life. His script has $$$N$$$ scenes with varying levels of excitement. For example, the scene of him studying for his first year exam was not very exciting, so Aram might rate it with an excitement level of $$$1$$$. On the other hand, the scene with Aram at ICPC World Finals was very exciting, so its excitement level might be $$$1\,000$$$.

Aram needs to split the play into $$$K$$$ acts. He knows that each act will only be remembered by the most exciting scene in it, so the excitement level of each act is the excitement level of the most exciting scene in the act. Since the scenes are chronologically ordered, each act must consist of a non-empty contiguous set of scenes. Every scene must appear in exactly one act.

The excitement of the play is the sum of excitements of the acts. Help Aram make the most exciting play!

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1\le K\le N \le 2\,000$$$), the number of scenes and acts, respectively.

The second line contains $$$N$$$ space-separated integers. The $$$i$$$'th integer is $$$a_i$$$ ($$$1\le a_i \le 1\,000$$$), the excitement level of the $$$i$$$th scene.

Output a single integer, the maximum total excitement of the whole play.

2 1
3 1

3

2 2
3 100

103