#include <bits/stdc++.h>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n,g,p[5005][10005],i,val,gr,j;
int main()
{
    fin>>n>>g;
    for(i=1; i<=n; i++)
    {
        fin>>gr>>val;
        if(val>p[i-1][gr])
            p[i][gr]=val;
        for(j=1; j+gr<=g; j++)
        {
            p[i][j+gr]=max(p[i-1][j+gr],val+p[i-1][j]);
        }
    }
    fout<<p[n][g];
    return 0;
}