#include <bits/stdc++.h>

using namespace std;

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

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


int main()
{
    int l1 = 0, l2 = 1;
    fin >> n >> G;
    for(int i = 1; i <= n; i++)
        fin >> g[i] >> v[i];

    dp[l1][g[1]] = v[1];
    for(int i = 2; i <= n; i++)
       {

            for(int j = 1; j <= G; j++)
            {
                dp[l2][j] = dp[l1][j];
                if(j >= g[i])
                    dp[l2][j] = max(dp[l2][j],
                                    v[i] + dp[l1][j - g[i]]);
            }
            swap(l1,l2);
       }


    fout << dp[l2][G];
    return 0;
}