题目描述

小 A 同学接到了 n 个需要完成的任务，这 n 个任务必须按照接到的顺序完成，每个任务的完成时间为 a_i 。由于任务非常艰巨，小 A 同学从秦老师那里领到了一张减负卡,用这张卡,小 A 可以从 n 个任务中任意的删除 k 个连续的任务，只需要完成剩余的任务。 请问，小 A 完成所有任务的总时间最少是多少 ?

输入样例

第1行，有两个整数 n 和 k ( 1 $\leq$ n $\leq$ 10⁶ , 0 $\leq$ k $\leq$ 10⁶ )。接下来有 n 个整数，每个整数 a_i 表示每个任务的完成时间。( 1 $\leq$ a_i $\leq$ 10¹² )

输出样例

一个整数，表示小 A 任务完成的最少时间。

样例

5 2
1 3 2 5 4

6

6 3
1000000 1000000 1000000 1000000 1000000 1000000

3000000

提示

连续删除 k 个任务，最后完成任务的时间最短。说明我们要删除区间长度内最大的区间和。