#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX(a, b) (a > b ? a : b)

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

void gen(int gr, int n)
{
    if (gr <= 0 || n <= 0)
        return;

    gen(gr - w[n - 1][0], n - 1);
    if (gr >= w[n-1][0]) {
        for (int i = 1; i <= n; i++)
            aux[i] = MAX(aux[i-1], v[i-1] + w[i-1][1]);
        for (int i = 1; i <= n; i++)
            v[i] = aux[i];
    } else {
        v[n] = v[n-1];
    }
}

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);

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