#include<bits/stdc++.h>
#define int __int128
#define maxn 500005
using namespace std;
namespace IO{
	inline int read(){
		int x=0,f=1;
		char ch=getchar();
		while(ch<'0'||ch>'9'){
			if(ch=='-')f=-1;
			ch=getchar();
		}
		while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
		return x*f;
	}
	inline void write(int x){
		if(x<0){putchar('-');x=-x;}
		if(x>=10)write(x/10);
		putchar(x%10+'0');return;
	}
}
using namespace IO;
int n,m,f[maxn],a[maxn],g[maxn],s[maxn],cntf[maxn],cntg[maxn];
int headg,tailg,qg[maxn];
int headf,tailf,qf[maxn];
inline int Yg(int i){return f[i]+s[i];}
inline int Xg(int i){return i;}
inline int Yf(int i){return i*a[i]-s[i]+g[i];}
inline int Xf(int i){return a[i];}
int wqs(int x){
	headg=headf=0;tailg=tailf=1;
	for(int i=1,j;i<=n;++i){
		while(headg<tailg&&(long double)(Yg(qg[headg+1])-Yg(qg[headg]))<=(long double)a[i]*(Xg(qg[headg+1]-qg[headg])))headg++;
		j=qg[headg];
		g[i]=i*a[i]-j*a[i]-s[i]+s[j]+f[j];
		cntg[i]=cntf[j];
		
		while(headf<tailf&&(long double)(Yf(qf[tailf])-Yf(qf[tailf-1]))*(Xf(i)-Xf(qf[tailf]))>=(long double)(Yf(i)-Yf(qf[tailf]))*(Xf(qf[tailf])-Xf(qf[tailf-1])))tailf--;
		qf[++tailf]=i;
		
		
		while(headf<tailf&&(long double)Yf(qf[headf+1])-Yf(qf[headf])<=(long double)i*(Xf(qf[headf+1])-Xf(qf[headf])))headf++;
		j=qf[headf];
		f[i]=-x+s[i]-s[j]+-(i-j)*a[j]+g[j];
		cntf[i]=cntg[j]+1;
		
		while(headg<tailg&&(long double)(Yg(qg[tailg])-Yg(qg[tailg-1]))*(Xg(i)-Xg(qg[tailg]))>=(long double)(Yg(i)-Yg(qg[tailg]))*(Xg(qg[tailg])-Xg(qg[tailg-1])))tailg--;
		qg[++tailg]=i;
		
	}
	return (cntf[n]);
}
signed main(){
	n=read();m=read();
	for(int i=1;i<=n;++i)a[i]=read();sort(a+1,a+1+n);
	for(int i=1;i<=n;++i)s[i]=s[i-1]+a[i];
	int l=-1e12,r=0,mid;int ans=0;
	while(l<=r){
		mid=(l+r)/2;
		if(wqs(mid)<=m)l=mid+1,ans=mid;
		else r=mid-1;
	}
	wqs(ans);
	write(f[n]+ans*m);
	return 0;
}