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

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

    printf("\n(n=%d) gr=%d:", n, gr);
    for (int i = 1; i <= n; i++)
        printf(" %d", v[i]);
}

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

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