#include <stdio.h>

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

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

void gen(int N, int gr)
{
    for (int n = 1; n <= N; n++)
       for (int i = gr; i >= 1; i--)
            if (i >= w[n - 1][0])
                v[i] = MAX(v[i], v[i - w[n - 1][0]] + w[n - 1][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(n, g);
    FILE *out = fopen("rucsac.out", "w");
    fprintf(out, "%d", v[g]);
    fclose(out);
}