#include <fstream>
#include <vector>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int n, G;
struct ob
{
    int w, p;
};
vector <ob> v;
int dp[5001][10001];
int main()
{
    cin >> n >> G;

    v.resize(n+1);
    for(int i=1; i<=n; i++)
        cin >> v[i].w >> v[i].p;
    for(int i=1; i<=n; i++)
        for(int j=0; j<=G; j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j >= v[i].w && dp[i-1][j-v[i].w] + v[i].p > dp[i][j])
                dp[i][j] = dp[i-1][j-v[i].w] + v[i].p;

        }
    cout << dp[n][G];
    return 0;
}