#include <bits/stdc++.h>

using namespace std;

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

#define limN 5002
#define limG 10002

int W[limN];
int P[limN];
int dp[2][limG];

int main()
{
    int n,gmax;
    fin>>n>>gmax;
    for(int i=1; i<=n; i++)
    {
        fin>>W[i]>>P[i];

    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=gmax; j++)
        {
            dp[i%2][j]=dp[(i-1)%2][j];
            if(W[i%2]<=j)
                dp[i%2][j]=max(dp[i%2][j],dp[(i-1)%2][j-W[i]]+P[i]);
        }
    }

    fout<<dp[n%2][gmax];
    return 0;
}

/*
    dp[i][j]=profitul maxim cu care putem avea o submultime de obiecte
    din primele i obiecte cu suma grutatilor = j

    //obiectul cu greutatea 3 si profitul 7;
    dp[1][3]=7;

    //vine obiectul cu greutatea 3 si profitul 4;
    dp[2][3]=max(dp[2][3],4);   //revenim
    dp[2][3+3]=max(dp[2][6],7+4);

    //vine obiectul cu greutatea 1 si profitul 2;
    dp[3][1]=2;
    dp[3][3+1]=

    !!!!!!!
    VARIANTA CORECTA IN CAIET
*/