#include<fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int n,G,a[10010],i,j,k,r;
pair<int,int> v[5010];
#define x first
#define y second

int main()
{
    fin>>n>>G;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
        for(j=1;j<=G;j++)
        {
            if(j%v[i].y==0)
                r=a[j];
            if(j-v[i].x>=0)
                a[j]=max(a[j],r+v[i].y);
        }
    }
    fout<<a[G];
    fin.close();
    fout.close();
    return 0;
}