// 
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define db long double
#define x first
#define y second
#define wdnmd const int mod=::mod;
#define eps 1e-12
#define lb(i) ((i)&(-(i)))
#define wr(x,ch) write(x),putchar(ch)
using namespace std;
typedef pair<int,char> paic;
typedef pair<int,int> pai;
typedef pair<pai,int> paii;
typedef pair<pai,pai> ppai;
typedef pair<ppai,int> ppaii;
pai operator+(const pai &x,const pai &y) {return pai(x.x+y.x,x.y+y.y);}
pai operator-(const pai &x,const pai &y) {return pai(x.x-y.x,x.y-y.y);}
#define gh() getchar()
inline long long read() {
	char ch=gh();
	long long x=0;
	char t=0;
	while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
	return t?-x:x;
}
void write(ll x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) write(x/10);
    putchar(x%10^48);
    return ;
}
typedef vector<pai> vec;
const int N=1e6+5,inf=0x3f3f3f3f;
vec dp[N];
int now,ans,cnt[N],n,S;
void ins(vec &x,pai t) {
	if(now+1<t.x) 
		x.push_back(t),now=t.y;
	else 
		x[x.size()-1].y=now=max(now,t.y);
	return ;
}
vec merge(vec &xx,int del,vec &y) {
	vec z,x;
	for(auto &lxl:xx) x.push_back(pai(lxl.x+del,lxl.y+del));
	int p=0,q=0;now=-inf;
	while(p<x.size()||q<y.size()) {
		if(q==y.size()||(p<x.size()&&x[p].x<y[q].x)) ins(z,x[p++]);
		else ins(z,y[q++]);
	}
	return z;
}
void add(int v,int w) {
	int del=-1,st=cnt[0]+S,ed=0;
	if(w<0) 
		swap(st,ed),del*=-1;
	for(int i=st;;i+=del) {
		if(dp[i].empty()) {
			if(i==ed) break;
			continue;
		}
		if(i+w<0||i+w>cnt[0]+S) continue;
		dp[i+w]=merge(dp[i],v,dp[i+w]);
		if(i==ed) break;
	}
	return ;
}
signed main() {
	n=read(),S=read();
	for(int i=1;i<=n;i++) 
		cnt[read()]++;
	dp[cnt[0]].push_back(pai(0,cnt[1]));
	for(int i=0;i<=S;i++) {
		if(i==1) continue;
		for(int j=0;j<=20;j++) 
			if((1<<j)<=cnt[i]) {
				cnt[i]-=(1<<j);
				add(1<<j,(i-1)*(1<<j));
			}
		if(cnt[i]) add(cnt[i],(i-1)*cnt[i]);
	}
	for(int i=0;i<=S+cnt[0];i++) 
		for(const auto &lxl:dp[i]) 
			ans+=lxl.y-lxl.x+1;
	wr(ans,'\n');
    return 0;
}