#include <stdio.h>

using namespace std;
const int N = 5001;
const int G = 10001;
int w[N], p[N], optim[G];
int main()
{
    FILE *in, *out;
    in = fopen ("rucsac.in", "r");
    out = fopen ("rucsac.out", "w");
    int n, g;
    fscanf(in ,"%d%d", &n, &g);
    int i;
    for(i = 1; i <=n; i++)
    {
        fscanf(in, "%d %d", &w[i], &p[i]);
    }
    optim[0] = 0;
    int j, s = 0;
    for(i = 1; i <=n; i++)
        for(j = g - w[i]; j >= 0; j--)
            if(optim[j+w[i]] < optim[j] + p[i])
            {
                optim[j+w[i]] = optim[j] + p[i];
                if(optim[j+w[i]] >= s)
                    s = optim[j+w[i]];
            }
    fprintf(out , "%d", s);
    return 0;
}