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

int v[10000][5000], 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];

    if (gr >= w[n][0])
        v[gr][n] = w[n][1] + gen(gr - w[n][0], n - 1);
    upmax(&v[gr][n], gen(gr, 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);
}