#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<climits>
#define int long long
#define getchar_unlocked() getchar()
using namespace std;
const int N=1e5+5;
int n,m,a[N],ans,c[N],die,b[N];
inline int lowbit(int x){
	return x&-x;
} 
void add(int x,int k){
	for(;x<=n;x+=lowbit(x)) c[x]+=k;
}
inline int ask(int x){
	int ans=0;
	for(;x;x-=lowbit(x)) ans+=c[x];
	return ans;
}
void add1(int x,int y,int k){
	add(x,k),add(y+1,-k);
}
inline int read(){
    int s=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') f=-1;
        ch=getchar_unlocked();
    }
    while(isdigit(ch)){
        s=(s<<3)+(s<<1)+(ch&15);
        ch=getchar_unlocked();
    }
    return s*f;
}
signed main(){
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	sort(a+1,a+1+n);
	if(m==0){
		for(int i=1;i<=n;i++) ans+=(i>1?a[i]:(a[i]-1))*(n-i+1);
		printf("%lld",ans);
		return 0;
	}
	for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1],add(i,b[i]);
//	cout<<ask(4)<<"\n";
	for(int i=1;i<=m;i++){
		if(n-die>=3){
			add1(die+1,n,-1);
			int l=die+1,r=n;
			while(l<=r){
				int mid=(l+r)/2;
				if(ask(mid)>0) r=mid-1;
				else l=mid+1;
			}
			die=r;
//			cout<<c[die]<<" "<<die<<" ";
			ans+=(n-die);
//			cout<<"1 ";
		}
		else if(n-die==2){
			if(ask(die+1)==1){
				if(ask(die+2)>1){
					add1(die+1,n,-1);
					die++,ans++;
					continue;
				}
				add1(die+1,n,-1);
				if(ask(die+1)==0) die++;
				if(ask(die+1)==0) die++; 
//				cout<<"2 ";
			}
			else{
//				add(die+1,-2);
				c[die+1]-=2;
				if(ask(die+1)<=0) die++,ans++;
				else ans+=2;
//				cout<<"3 ";
			}
		}
		else{
			add(die+1,-2);
//			c[die+1]-=2; 
			if(ask(die+1)<=0) die++;
			else ans++;
//			cout<<"4 ";
		}
//		cout<<"-----\n result:"<<ans<<"\n"<<"     "<<ask(1)<<"\n------\n";
	}
//	cout<<"QWQ"<<ans<<" "<<die+1<<"\n";
	for(int i=die+1;i<=n;i++) ans+=(ask(i)-1)*(n-i+1)+(n-i);
	printf("%lld",ans);
	return 0;
}
/*
hack

1 5
18600947

18600941
*/