#include <bits/stdc++.h>

using namespace std;

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

const int N_MAX = 1e4 + 5;

int dp[N_MAX];
int n, G;

int main(){
   ios_base::sync_with_stdio(false);

    fin >> n >> G;
    fill(dp, dp + G + 1, -1);
    dp[0] = 0;
    for (int i = 1; i <= n; i++){
        int g, p; fin >> g >> p;
        for (int j = G; j > 0; j--){
            if (j - g < 0){
                continue;
            }
            if (dp[j - g] != -1){
                if (dp[j] == -1){
                    dp[j] = dp[j - g] + p;
                }
                else{
                    dp[j] = max(dp[j], dp[j - g] + p);
                }
            }
        }
    }
    fout << *max_element(dp, dp + G + 1);
}