#include<cstdio>
#define FOR1 for(i=1;i<=n;++i)
#define FOR2 for(j=1;j<=G;++j)
using namespace std;
struct obiect {int g,c;} a[20];
int n,i,j,G,C[20][20];
int main()
{
 freopen("rucsac.in","rt",stdin);
 freopen("rucsac.out","wt",stdout);
 scanf("%d%d",&n,&G);
 FOR1 scanf("%d%d",&a[i].g,&a[i].c);
 FOR1 FOR2 if(a[i].g<=j && ( a[i].c + C[i-1][j-a[i].g] ) >= C[i-1][j]) C[i][j]=a[i].c + C[i-1][j-a[i].g]; else C[i][j]=C[i-1][j];
 printf("%d\n",C[n][G]);
 return 0;
}