#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;

int v[10000][5000], w[10000][2];

int gen(int gr, int n)
{
    if (gr <= 0 || n < 0)
        return 0;
    if (v[gr][n] != 0)
        return v[gr][n];
    
    v[gr][n] = gen(gr, n - 1);
    if (gr >= w[n][0])
        v[gr][n] = max(v[gr][n], w[n][1] + gen(gr - w[n][0], n - 1));
    return v[gr][n];
}

int main()
{
    FILE *in = fopen("rucsac.in", "r");

    int n, g;
    fscanf(in, "%d%d", &n, &g);
    for (int i = 0; i < n; i++)
        fscanf(in, "%d%d", &w[i][0], &w[i][1]);
    fclose(in);

    n = gen(g, n - 1);
    FILE *out = fopen("rucsac.out", "w");
    fprintf(out, "%d", n);
    fclose(out);
}