#include <bits/stdc++.h>

using namespace std;

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

int g[5005],v[5005];
int dp[2][10005];

int main()
{
    int n,r;
    fin >> n >> r;
    for (int i=1;i<=n;++i){
        fin >> g[i] >> v[i];
    }
    for (int k=1;k<=n;++k){
        for (int j=1;j<=r;++j){
            if (j>=g[k]){
                dp[1][j] = max(dp[0][j],dp[0][j-g[k]]+v[k]);
            }else{
                dp[1][j] = dp[0][j];
            }
        }
        for (int i=1;i<=r;++i){
            dp[0][i] = dp[1][i];
        }
    }
    int MAX = -999999999;
    for (int i=1;i<=r;++i){
        if (dp[0][i]>MAX) MAX = dp[0][i];
    }
    fout << MAX;
    return 0;
}