#include <iostream>
#include <fstream>

using namespace std;

int N, G, W[10000], P[10000], dp[10000][10000];

int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");

    f >> N >> G;

    for (int i = 1; i <= N;i ++) f >> W[i] >> P[i];

    for (int i = 0; i <= N; i ++)
        for (int j = 0; j <= G; j++){
            cout<<i<<" "<<j<<endl;
            if (i==0 || j==0) dp[i][j] = 0;
            else {if (W[i] <= j)
                dp[i][j] = max (dp[i-1][j], dp[i-1][j - W[i]] + P[i]);
                else dp[i][j] = dp[i-1][j];}
        }

    g << dp[N][G];

    return 0;
}