#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f
using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n,G,greutate[5005],cost[5005],total[10005];

int main()
{
    f>>n>>G;
    for(int i=1;i<=n;++i)
        f>>greutate[i]>>cost[i];

    total[0]=0;

    for(int i=1;i<=n;++i)
        for(int j=G;j>=0;--j)
        if(j+greutate[i]<=G)
        {
            total[j+greutate[i]]=max(total[j+greutate[i]],total[j]+cost[i]);
        }
    g<<total[G];
    return 0;
}