#include <bits/stdc++.h>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int a[5001][10001];
int v[10000], p[10000];
int main()
{
    int n, G,i,j;
    f>>n>>G;
    for(i=1;i<=n;i++)
        f>>v[i]>>p[i];
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=G;j++)
        {
            if(j-v[i]>=0)
            a[i][j]=max(a[i-1][j],a[i-1][j-v[i]]+p[i]);
            else
                a[i][j]=a[i-1][j];
        }
    }
    g<<a[n][G];
    return 0;
}