#include <bits/stdc++.h>

using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int m[5003][10003];
int n, g;
struct Numar
{
    int g;
    int p;
};
Numar v[5003];
int main()
{
    fin >> n >> g;
    for ( int i = 1 ; i <= n ; i++ )
        fin >> v[i].g >> v[i].p;
    for ( int i = 1 ; i <= n ; i++ )
    {
        for ( int j = 1 ; j <= g ; j++ )
        {
            m[i][j] = m[i-1][j];
        }
        for ( int j = v[i].g ; j <= g ; j++ )
        {
            int aux = m[i-1][j-v[i].g] + v[i].p;
            m[i][j] = max(aux, m[i][j]);
        }
    }
    fout << m[n][g] << endl;
    int a = n;
    int b = g;
    while ( a >= 1 && b >= 1 )
    {
        if ( m[a][b] == m[a-1][b] )
        {
            a--;
            continue;
        }
        //fout << a << " ";
        b = b - v[a].g;
        a--;
    }
    return 0;
}