链接：https://ac.nowcoder.com/acm/contest/3003/H

牛可乐有 n 个元素( 编号 1..n )，第 i 个元素的能量值为 a_iai​。
牛可乐可以选择至少 k 个元素来施放一次魔法，魔法消耗的魔力是这些元素能量值的极差。形式化地，若所用元素编号集合为 S，则消耗的魔力为 \max_{i\in S}\{a_i\}-\min_{i\in S}\{a_i\}maxi∈S​{ai​}−mini∈S​{ai​}。

牛可乐要求每个元素必须被使用恰好一次。
牛可乐想知道他最少需要多少魔力才能用完所有元素，请你告诉他。

输入描述:

第一行两个正整数 \text{}n, kn,k 。

第二行 n 个整数 a_1,a_2,\dots,a_na1​,a2​,…,an​。

保证 1\leq k\leq n\leq 3\times 10^51≤k≤n≤3×105，0\leq a_i\leq 10^90≤ai​≤109。

输出描述:

输出一行，一个整数表示答案。

示例1

输入

复制

4 2
8 7 114514 114513

输出

复制

2

说明

使用第 1、2 个元素施放一次魔法，消耗魔力为 8-7=1；第 3、4 个元素施放一次魔法，消耗魔力为 114514-114513=1；两个魔法一共消耗 2 点魔力。

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,t,g,k,l,o,s,r,ans,ss,max1=0;
long long a[4000001],dp[1000001];
int main()
{
	scanf("%lld %lld",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		dp[i]=1e9+7;
	}
    sort(a+1,a+1+n);
    long long min1=-a[1];
    for(int i=k;i<=n;i++)
    {
    	dp[i]=min1+a[i];
    	min1=min(min1,dp[i-k+1]-a[i-k+2]);
    }
    printf("%lld",dp[n]);
}