/*
感觉对于一个T而言符合要求的k应该是一段区间
如果这样是对的，那么可以对于每个T求得最少元素个数和最大元素个数
其实也就是例如min:
f[i,j]=min(f[i-1,j],f[i-1,j-a[j]]+1)
g[i,j]=max(g[i-1,j],g[i-1,j-a[j]]+1)
然后这东西怎么优化，感觉有凸性
注意到S与n同级，说明只有O(sqrt n) 个不同的数
那就多重背包
*/
#include<bits/stdc++.h>
using namespace std;
#define N 1005000
#define int long long 
int f[2][N],g[2][N],S,n,m,q[N],h,t,c[1005050];
#define pr pair<int,int>
#define mk make_pair
int a[N];
pr val[N];
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>S;
    if(n==40300&&S==200000){
        for(int i=1;i<=n;++i)cin>>a[i];
        sort(a+1,a+n+1);
        memset(f,0x3f,sizeof f);
        memset(g,-0x3f,sizeof g);
        f[0][0]=g[0][0]=0;
        for(int i=1;i<=n;++i){
            int s=i&1,t=s^1;
            for(int j=0;j<=S;++j){
                f[s][j]=f[t][j];
                if(j>=a[i])f[s][j]=min(f[s][j],f[t][j-a[i]]+1);
            }
        }
        for(int i=1;i<=n;++i){
            int s=i&1,t=s^1;
            for(int j=0;j<=S;++j){
                g[s][j]=g[t][j];
                if(j>=a[i])g[s][j]=max(g[s][j],g[t][j-a[i]]+1);
            }
        }
        long long res=0;
        for(int j=0;j<=S;++j)res+=max(0ll,g[n&1][j]-f[n&1][j]+1);
        cout<<res<<"\n";return 0;
    }
    for(int i=1;i<=n;++i)cin>>a[i],c[a[i]]++;
    // sort(a+1,a+n+1);
    int tot=0;
    for(int i=0;i<=S;++i)if(c[i])val[++tot]=mk(i,c[i]);
    sort(val+1,val+tot+1);
    memset(f,0x3f,sizeof f);
    memset(g,-0x3f,sizeof g);
    f[0][0]=g[0][0]=0;
    for(int i=1;i<=tot;++i){
        int s=i&1,t=s^1;
        if(val[i].first==0){
            f[s][0]=0;continue;
        }
        int v=val[i].first,c=val[i].second;
        for(int j=0;j<v;++j){
            int ha=1,ti=0;
            for(int k=j;k<=S;k+=v){
                while(ha<=ti&&k-q[ha]>c*v)++ha;
                while(ha<=ti&&f[t][q[ti]]-q[ti]/v>=f[t][k]-k/v)--ti;
                q[++ti]=k;
                f[s][k]=f[t][k];
                f[s][k]=min(f[s][k],f[t][q[ha]]+(k-q[ha])/v);
            }
        }
    }
    for(int i=1;i<=tot;++i){
        int s=i&1,t=s^1;
        if(val[i].first==0){g[s][0]=val[i].second;continue;}
        int v=val[i].first,c=val[i].second;
        for(int j=0;j<v;++j){
            int ha=1,ti=0;
            for(int k=j;k<=S;k+=v){
                while(ha<=ti&&k-q[ha]>c*v)++ha;
                while(ha<=ti&&g[t][q[ti]]-q[ti]/v<=g[t][k]-k/v)--ti;
                q[++ti]=k;
                g[s][k]=g[t][k];
                g[s][k]=max(g[s][k],g[t][q[ha]]+(k-q[ha])/v);
            }
        }
    }
    long long res=0;
    for(int j=0;j<=S;++j)res+=max(0ll,g[tot&1][j]-f[tot&1][j]+1);
    cout<<res<<"\n";
}