#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int dp[10001][10001];
int maxx,ans=-1,n,i,j;

int main()
{
    int x,y,gmax,v[10001],w[10001];
    fin >> n >> gmax;
    for (i=1; i<=n; i++)
    {
        fin >> y >> x;
        v[i]=x;
        w[i]=y;
    }
    dp[1][0]=0;
    for (j=1; j<=gmax; j++) dp[1][j]=INT_MIN;
    dp[1][w[1]]=v[1];
    for (i=1; i<=n; i++)
    {
        for (j=0; j<=gmax; j++)
        {
            if (j >= w[i])
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
            else dp[i][j]=dp[i-1][j];
            ans = max(ans,dp[i][j]);
        }
    }
    fout << ans;

}