#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

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

int n,G,greutate[5005],cost[5005],total[10005];

int main()
{
    f>>n>>G;
    for(int i=1;i<=n;++i)
        f>>greutate[i]>>cost[i];

    memset(total,INF,sizeof(total));
    total[0]=0;

    for(int i=1;i<=n;++i)
        for(int j=G;j>=0;--j)
        if(total[j]!=INF && j+greutate[i]<=G)
        {
            if(total[j+greutate[i]]<total[j]+cost[i] || total[j+greutate[i]]==INF)
            {
                total[j+greutate[i]]=total[j]+cost[i];
            }
        }
    g<<total[G];
    return 0;
}