#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
const int N=2e5+5;
int n,S,a[N];
struct Info{
	int len,seg[2][2];
	// void dbg() const{
	// 	if(!len){
	// 		debug("{}");
	// 	}else if(len==1){
	// 		debug("{[%d,%d]}",seg[0][0],seg[0][1]);
	// 	}else{
	// 		debug("{[%d,%d],[%d,%d]}",seg[0][0],seg[0][1],seg[1][0],seg[1][1]);
	// 	}
	// }
	void operator+=(const Info& rhs){
		vector<pair<int,int>> vec;
		For(i,0,len-1){
			vec.emplace_back(seg[i][0],-1);
			vec.emplace_back(seg[i][1]+1,1);
		}
		For(i,0,rhs.len-1){
			vec.emplace_back(rhs.seg[i][0],-1);
			vec.emplace_back(rhs.seg[i][1]+1,1);
		}
		sort(range(vec));
		int cur=0,seg_[2][2]{},len_=0,st=0;
		For(i,0,int(vec.size())-1){
			auto [l,x]=vec[i];
			cur+=x;
			if(bool(cur)!=bool(st)){
				if(cur){
					seg_[len_][0]=l;
				}else{
					seg_[len_++][1]=l-1;
				}
				st^=1;
			}
		}
		len=len_;
		memcpy(seg,seg_,sizeof(seg));
	}
	Info operator<<(int x){
		Info info=*this;
		For(i,0,len-1){
			info.seg[i][0]+=x;
			info.seg[i][1]+=x;
		}
		return info;
	}
}f[N];
struct SegmentTree{
	struct Node{
		int mn,mnc,add;
	}t[N*8];
	void apply(int p,int x){
		t[p].mn+=x;
		t[p].add+=x;
	}
	void push(int p){
		if(t[p].add){
			apply(p*2,t[p].add);
			apply(p*2+1,t[p].add);
			t[p].add=0;
		}
	}
	void pull(int p){
		t[p].mn=min(t[p*2].mn,t[p*2+1].mn);
		t[p].mnc=(t[p*2].mn==t[p].mn)*t[p*2].mnc+(t[p*2+1].mn==t[p].mn)*t[p*2+1].mnc;
	}
	void init(int p=1,int L=0,int R=n+S){
		t[p].mnc=R-L+1;
		if(L==R) return;
		int mid=(L+R)/2;
		init(p*2,L,mid);
		init(p*2+1,mid+1,R);
	}
	void range_add(int l,int r,int x,int p=1,int L=0,int R=n+S){
		if(l<=L&&R<=r){
			apply(p,x);
			return;
		}
		push(p);
		int mid=(L+R)/2;
		if(l<=mid){
			range_add(l,r,x,p*2,L,mid);
		}
		if(r>mid){
			range_add(l,r,x,p*2+1,mid+1,R);
		}
		pull(p);
	}
}seg;
vector<tuple<int,int,int>> cmd[N*2];
int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>S;
	map<int,int> cnt;
	For(i,1,n){
		cin>>a[i];
		++cnt[a[i]];
	}
	int sum=0;
	auto push=[&](int x,int c){
		Dec(i,sum,0){
			f[i+x]+=f[i]<<c;
		}
		sum+=x;
	};
	f[0].len=1;
	f[0].seg[0][0]=f[0].seg[0][1]=0;
	for(auto [x,c]:cnt){
		if(!x) continue;
		for(int i=1;i<=c;i<<=1){
			push((x-1)*i,i);
			c-=i;
		}
		if(c){
			push((x-1)*c,c);
		}
	}
	int c0=cnt[0];
	For(i,0,sum){
		For(j,0,f[i].len-1){
			auto [l,r]=f[i].seg[j];
			l+=i;
			r+=i;
			cmd[i-c0+N].emplace_back(l,r,1);
			cmd[i+1+N].emplace_back(l,r,-1);
		}
	}
	ll ans=0;
	seg.init();
	For(i,0,N*2-1){
		for(auto [l,r,w]:cmd[i]){
			seg.range_add(l,r,w);
		}
		if(seg.t[1].mn){
			ans+=n+S+1;
		}else{
			ans+=n+S+1-seg.t[1].mnc;
		}
	}
	cout<<ans<<'\n';
	return 0;
}