#include <iostream>
#include <fstream>
using namespace std;long n,W,p[1002],w[1002],a[1003][5003];
ifstream f("energii.in");
ofstream g("energii.out");
void citirea(){
f>>n>>W;
for(int i=1;i<=n;i++) f>>w[i]>>p[i];}

int main()
{
    citirea();
    for(int i=1;i<=W;i++) if(w[1]>=i) a[1][i]=p[i];
    for(int i=0;i<=1001;i++) for(int j=0;j<=1001;j++) if(a[i][j]==0)a[i][j]=10000;
    for(int i=2;i<=n;i++)
    for(int x=0;x<=W;x++){
       if(w[i]>=x)a[i][x]=min(a[i-1][x],p[i]);
        else a[i][x]=min(a[i-1][x],a[i-1][x-w[i]]+p[i]);   }
// for(int i=0;i<=n;i++) {for(int j=0;j<=W;j++)cout<<a[i][j]<<" ";cout<<endl;}
 g<<a[n][W];
    return 0;
}