CF1175G.Yet Another Partiton Problem

You are given array $a_1, a_2, \dots, a_n$. You need to split it into $k$ subsegments (so every element is included in exactly one subsegment).

The weight of a subsegment $a_l, a_{l+1}, \dots, a_r$ is equal to $(r - l + 1) \cdot \max\limits_{l \le i \le r}(a_i)$. The weight of a partition is a total weight of all its segments.

Find the partition of minimal weight.

给你一个数组 $a_1, a_2, \dots, a_n$。你需要将其划分为 $k$ 个子段（即每个元素恰好属于其中一个子段）。

子段 $a_l, a_{l+1}, \dots, a_r$ 的权重定义为 $(r - l + 1) \cdot \max\limits_{l \le i \le r}(a_i)$。一个划分的权重定义为该划分中所有子段的权重之和。

请找出权重最小的划分。

The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^4$, $1 \le k \le \min(100, n)$) — the length of the array $a$ and the number of subsegments in the partition.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^4$) — the array $a$.

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^4$，$1 \le k \le \min(100, n)$）—— 分别表示数组 $a$ 的长度以及划分中子区间的个数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2 \cdot 10^4$）—— 数组 $a$。

Print single integer — the minimal weight among all possible partitions.

输出一个整数——所有可能划分中最小的权重。

The optimal partition in the first example is next: $6$ $1$ $7$ $\bigg|$ $4$.

The optimal partition in the second example is next: $6$ $\bigg|$ $1$ $\bigg|$ $7$ $4$.

One of the optimal partitions in the third example is next: $5$ $\bigg|$ $1$ $5$ $\bigg|$ $1$ $\bigg|$ $5$.

第一个样例的最优划分如下：$6$ $1$ $7$ $\bigg|$ $4$。

第二个样例的最优划分如下：$6$ $\bigg|$ $1$ $\bigg|$ $7$ $4$。

第三个样例的一个最优划分如下：$5$ $\bigg|$ $1$ $5$ $\bigg|$ $1$ $\bigg|$ $5$。