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

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

const int gmax = 10005;
int dp[gmax];

int main() {
    ios_base :: sync_with_stdio(false);
    int n, g, p, w, i, j, sol = 0;
    fin >> n >> g;
    dp[0] = 0;
    for(i = 1; i <= n; i++) {
        fin >> w >> p;
        for(j = g - w; j >= 0; j--) {
            if(dp[j + w] < dp[j] + p) {
                dp[j + w] = dp[j] + p;
                if(dp[j + w] > sol) {
                    sol = dp[j + w];
                }
            }
        }
    }
    fout << sol;
    fin.close();
    fout.close();
    return 0;
}