题目描述

本题题解已发表至 讨论区

当时我还是个崭新锃亮的大一生，无数的社团传单被递到我面前，远超我脑容量的信息扑面而来。在我看来，仿佛都是通向玫红色校园生活的大门。而我最终选择的是——双创中心实验室。门后确实有纯金的光辉未来，黑发少女们跃然银幕之上，可谓是爱情新浪潮电影天堂。
我被clh学长莫名其妙的代码搞得火大，而不知不觉间，在我身边出现了一个面貌极度不详，让人毛骨悚然的男人。

“这……这是月球背面的人吗，还是外星人？”

“你说得太难听了吧，放心好了，我是和你站在同一边的。这就是我的爱啊，我们被命运的黑线连在一起了。”

这便是我和小津的第一次接触，同时也是最糟糕的接触。小津跟我是同届的，他讨厌蔬菜，一天到晚只吃方便食品。张着一张仿佛来自月球背面的脸，极其瘆人。他欺负弱者，巴结强者，懒惰，爱跟人对着干，如果没遇见他，想必我的灵魂会更加纯洁吧。

我和小津为了吹响反抗clh学长派系的号角，决定自己开始拍摄电影。奇怪的是，似乎我们越努力，clh学长的魅力就越发闪耀。现在回想起来，我们被当成了杠杆的支点，为的是抬高学长的魅力。我们不甘输给clh学长，准备公布正在拍摄的爱情电影新作，结果遭到学长派系的一致反对。敌人的先锋，chx学长是clh学长的左膀右臂，也是对我们百般刁难的人，用出各种阴招将我赶出了603。

“为什么那种人倍受追捧，我们却只能忍受着这种待遇！”

"这是clh学长的成绩单，别看他表面那么强势，实际处境惨不忍睹。"

“他都读八年了吗?而且成绩相当悬，都在及格线边缘。小津，我有个主意，你愿意帮我吗？我要制裁clh学长。”

“好吧，我会永远追随你的，导演。”

我决定拍一部纪录片揭发clh学长的恶行！

小津如鱼得水，越来越来劲，不断被改编的胶片早已脱离事实，从揭发电影成了纯主观的诽谤电影。但是这样还不够，我要把这个长度为$n$的片子$a$剪成$k$个片段，再进行传播，这样一定能最大化诽谤效果。我拿起了胶卷，开始了思考。

一个片段可以看作是一个长度为$m$的数组$b$。如果在$i$处剪辑需要花费我$b_i$的精力才能把b剪成$b_1$……$b_{i-1}$和$b_{i+1}$……$b_{m}$，共两个片段，$b_i$将永远从世界上消失。特别地，如果$i=1$，这个片段将被剪成$b_2$……$b_m$，共一个片段。$i=m$同理。

所以我要把片子剪成$k$个片段至少要花费多少精力？

输入描述

第一行输入两个整数$n,k$，表示数组$a$的长度和需要剪出的片段数量

第二行输入$n$个整数$a_i$

$3≤n≤2000$

$1≤k≤100$

$0≤a_i≤2e5$

输出描述

一个整数，表示我至少需要花费的精力

示例 1

输入

6 3
1 3 2 4 6 1

输出

7

说明

在2处剪辑后原片段将变为{1},{2,4,6,1}，随后在后者的2处剪辑，最终得到{1},{2},{6,1}共3个片段。所以最终结果为3+4=7