#include <bits/stdc++.h>

using namespace std;

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

int n, g;
int dp[2][10005];

int main()
{
    int L = 1;
    fin >> n >> g;
    for(int i = 1; i <= n; i ++, L = 1 - L)
    {
        int w, p;
        fin >>  w >> p;
        for(int j = 0; j <= g; j ++)
        {
            dp[L][j] = dp[1 - L][j];
            if(j >= w)
            {
                dp[L][j] = max(dp[L][j], dp[1 - L][j - w] + p);
            }
        }
    }
    L = 1 - L;
    int ma = 0;
    for(int i = 0; i <= g; i ++)
    {
        ma = max(dp[L][i], ma);
    }
    fout << ma;
    return 0;
}