#include <cstdio>
using namespace std;
const int maxn = 5005;

int price[maxn];
int weight[maxn];
int best[10005];
inline int max(int a,int b)
{
    if(a>b)
        return a;
    return b;
}
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    int n,g,i,j;
    scanf("%d %d",&n,&g);
    for(i=1;i<=n;++i)
        scanf("%d %d",&weight[i],&price[i]);
    for(i=1;i<=n;++i)
        for(j=g;j-weight[i]>=0;--j)
            best[j] = max(best[j],best[j-weight[i]]+price[i]);
    printf("%d\n",best[g]);
    return 0;
}