#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    int n,g;
    fin>>n>>g;
    int **dp,w[5001],p[5001];

    dp = new int*[n+1];
    for(int i=0;i<=n;i++) dp[i] = new int[g+1];
    for(int i=1;i<=n;i++){
        fin>>w[i]>>p[i];
    }

    for(int i=0;i<=g;i++){
        dp[0][i] = 0;
    }

    for(int i=0;i<=n;i++) dp[i][0] = 0;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=g;j++){
            int x1 = dp[i-1][j];
            int x2 = 0;
            if(j-w[i]>=0) x2 = dp[i-1][j-w[i]] + p[i];
            dp[i][j] = max(x1,x2);
        }
    }

    fout<<dp[n][g];
    return 0;
}