#include <bits/stdc++.h>

using namespace std;

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

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

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];
    int cur=1,nxt=2;
    for (i=1; i<=n; i++)
    {

        for (j=0; j<=gmax; j++)
        {
            dp[nxt][j]=dp[cur][j];
            if (j >= w[i] && dp[cur][j-w[i]] != INT_MIN) {
                dp[nxt][j] = max(dp[nxt][j], dp[cur][j-w[i]] + v[i]);
            }
        }
        swap(cur,nxt);
    }
    for (int j=0; j<=gmax; j++) ans = max(ans, dp[2][j]);
    fout << ans;

}