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

int w[10000][2];

void upmax(int *a, int b)
{
    if (b > *a)
        *a = b;
}

int gen(int gr, int n)
{
    if (gr <= 0 || n < 0)
        return 0;
    // if (v[gr][n] != 0)
    //     return v[gr][n];

    int v = gen(gr, n - 1);
    if (gr >= w[n][0])
        upmax(&v, w[n][1] + gen(gr - w[n][0], n - 1));
    return v;
}

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