#include <stdio.h>
#include <iostream>

using namespace std;

FILE *fin = fopen("rucsac.in", "r");
FILE *fout = fopen("rucsac.out", "w");

int n,g,i,j,dp[10005],w[5005],p[5005];

int main()
{
    fscanf(fin, "%d%d", &n,&g);
    for(i=1; i<=n; ++i)
        fscanf(fin, "%d%d", &w[i],&p[i]);

    for(i=1; i<=n; ++i)
        for(j=g; j>=w[i]; --j)
            dp[j] = max(dp[j], dp[j-w[i]]+p[i]);

    fprintf(fout, "%d", dp[g]);

    fclose(fin);
    fclose(fout);
    return 0;
}