#include <iostream>
#include <fstream>
using namespace std;

int knapsack(int wt[], int val[], int n, int c)
{
    int v[n+1][c+1];

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

int main()
{
    int n, c, wt[5000], val[5000];
    ifstream f;
    f.open("rucsac.in");
    f >> n >> c;
    for (int i = 0; i < n; i++)
        f >> wt[i] >> val[i];

    ofstream g;
    g.open("rucsac.out");

    g << knapsack(wt, val, n, c);

    f.close();
    g.close();
    return 0;
}