g6-07906. 划分型·最大段极值 未做

给定 $n$ 个整数 $a_1,\dots ,a_n$，把它分成恰好 $k$ 段连续段。每段的得分是段内最小值。求最大总得分。

第一行两个整数 $n,k$。

第二行 $n$ 个整数。

一行一个整数，表示最大总得分。

输入 1

5 2
1 2 3 4 5

输出 1

6

对于所有数据，$1\le k\le n\le 300$，$1\le a_i\le 10^9$。