#include <stdio.h>

int max(int a, int b)
{
    return (a > b) ? a : b;
}

int rucsacDinamic(int W, int wt[], int val[], int n)
{
    int i, w;
    int K[n + 1][W + 1];
    for (i = 0; i <= n; i++)
    {
        for (w = 0; w <= W; w++)
        {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (wt[i - 1] <= w)
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
            else
                K[i][w] = K[i - 1][w];
        }
    }
    return K[n][W];
}

int main()
{
    FILE *in = fopen("rucsac.in", "r");
    FILE *out = fopen("rucsac.out", "w");
    int N, G;
    fscanf(in, "%d %d", &N, &G);
    int profit[N], greutate[N];
    for (int i = 0; i < N; i++)
    {
        fscanf(in, "%d %d", &greutate[i], &profit[i]);
    }
    fprintf(out, "%d", rucsacDinamic(G, greutate, profit, N));
    fclose(in);
    fclose(out);
    return 0;
}