[USACO19OPEN]Snakes G

题目描述

传说,数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而,蛇们现在卷土重来了!圣帕特里克节是在每年的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 $ 和 $ K $ 。 第二行包含 $ N $ 个整数 $ a_1, \ldots ,a_N $ ,其中 $ a_i $ ( $ 0 \leq a_i \leq 10^6 $ )为第 $ i $ 组蛇的数量。

输出格式


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

输入输出样例

输入样例 #1

6 2
7 9 8 2 3 2

输出样例 #1

3

说明

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