#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,v[999999],w[999999],ans=0;
void    dfs(int x,int y,int z)
{
    if(x==n+1)    if(y>m)    return ;
                    else    {ans=max(ans,z);return;}
    else{
        dfs(x+1,y+v[x],z+w[x]);
        dfs(x+1,y,z);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);
    dfs(1,0,0);
    cout<<ans;
    return 0;
}

 #define INF 100099
int n,m,v[999999],w[999999],ans=0;
int dfs(int x,int y)
{
    if(x==n+1)    if(y>m)    return -INF;
                    else    {return 0;}
    else
    return    max(dfs(x+1,y+v[x])+w[x],dfs(x+1,y)); 

}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);    
    cout<<dfs(1,0);
    return 0;
}

 int n,m,v[9999],w[9999],ans=0,dp[9999][9999];
int dfs(int x,int y)
{
    if(y>m)    return -INF;
    if(x==n+1)     return 0;    
    if (dp[x+1][y+v[x+1]])
    dp[x][y]=max(dp[x+1][y+v[x]]+w[x],dp[x][y]);
        else
    dp[x][y]=max(dfs(x+1,y+v[x])+w[x],dp[x][y]);
    
    if (dp[x+1][y])
    dp[x][y]=max(dp[x+1][y],dp[x][y]); 
    else
    dp[x][y]=max(dfs(x+1,y)+w[x],dp[x][y]);
    return dp[x][y];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);                
    cout<<dfs(1,0)<<" "<<dp[0][0];
    return 0;
}


#define INF 100099
int n,m,v[9999],w[9999],ans=0,dp[9999][9999];
int dfs(int x,int y)
{
    if(y>m)    return -INF;
    if(x==n+1)     return 0;    
    if (dp[x+1][y+v[x+1]])
    dp[x][y]=max(dp[x+1][y+v[x]]+w[x],dp[x][y]);
        else
    dp[x][y]=max(dfs(x+1,y+v[x])+w[x],dp[x][y]);
    
    if (dp[x+1][y])
    dp[x][y]=max(dp[x+1][y],dp[x][y]); 
    else
    dp[x][y]=max(dfs(x+1,y),dp[x][y]);
    return dp[x][y];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);    
    for(int i=n;i>=1;i++)
        for(int j=1;j<=m;j++)
            dp[i][j]=max(dp[i+1][j])
    return 0;
}