#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int N, W;
int D[2][10010];

int main()
{
    ifstream i("rucsac.in");
    ofstream o("rucsac.out");

    i >> N >> W;

    for(int a = 1; a <= N; a++)
    {
        int j, k;

        i >> k >> j;

        for(int b = 0; b <= W; b++)
        {
            D[0][b] = D[1][b];
        }

        for(int b = 0; b <= W; b++)
        {
            D[1][b] = D[0][b];

            if(b >= k)
            {
                D[1][b] = max(D[1][b], D[0][b - k] + j);
            }
        }
    }

    o << D[1][W];

    return 0;
}