#include <bits/stdc++.h>

using namespace std;

FILE *fin, *fout;

int dp[2][10001];

int main()
{
    fin = fopen("rucsac.in" , "r");
    fout = fopen("rucsac.out" , "w");

    int n, g, w, p;

    fscanf(fin , "%d %d", &n, &g);
    for(int i = 0 ; i < n ; ++i){
        fscanf(fin , "%d %d", &w, &p);
        for(int j = 1 ; j <= g ; ++j)
            dp[0][j] = dp[1][j];
        for(int j = 1 ; j <= g ; ++j){
            if(w <= j)
                dp[1][j] = max(dp[0][j] , dp[0][j-w]+p);
        }
    }
    fprintf(fout , "%d" , dp[1][g]);
    return 0;
}