题目描述

传说，数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而，蛇们现在卷土重来了！圣帕特里克节是在每年的3月17日，所以Bessie要用彻底清除哞尔兰所有的蛇来纪念圣帕特里克。

Bessie装备了一个捕网，用来捕捉 $N$ 组排成一行的蛇（ $1 \leq N \leq 400$ ）。Bessie必须按照这些组在这一行中出现的顺序捕捉每一组的所有蛇。每当Bessie抓完一组蛇之后，她就会将蛇放在笼子里，然后带着空的捕网开始捕捉下一组。

一个大小为 $s$ 的捕网意味着Bessie可以抓住任意包含 $g$ 条的一组蛇，其中 $g \leq s$ 。然而，每当Bessie用大小为 $s$ 的捕网抓住了一组 $g$ 条蛇，就意味着浪费了 $s-g$ 的空间。Bessie可以任意设定捕网的初始大小，并且她可以改变 $K$ 次捕网大小（ $1 \leq K<N$ ）。

请告诉Bessie她捕捉完所有组的蛇之后可以达到的总浪费空间的最小值。

输入格式

输入的第一行包含 $N$ 和 $K$ 。

第二行包含 $N$ 个整数 $a_1, \ldots ,a_N$ ，其中 $a_i$ （ $0 \leq a_i \leq 10^6$ ）为第 $i$ 组蛇的数量。

输出格式

输出一个整数，为Bessie抓住所有蛇的总浪费空间的最小值。

6 2
7 9 8 2 3 2

3

提示

Bessie可以设置她的捕网开始时大小为7。当她抓完第一组蛇之后，她将她的捕网的大小调整为9，保持这个大小直到抓完第4组蛇，再将捕网大小调整为3。总浪费空间为 $(7-7)+(9-9)+(9-8)+(3-2)+(3-3)+(3-2)=3$ 。