#include <bits/stdc++.h>
#define maxn 100001
using namespace std;
ifstream f("energii.in");
ofstream g("energii.out");
int n,m,i,j,cost[maxn],energie[maxn],l=1,a[2][maxn];
int main()
{ f>>n>>m;
  for(i=1;i<=n;i++)
        f>>energie[i]>>cost[i];
  for(i=1;i<=maxn;i++)
    a[0][i]=a[1][i]=maxn;
  for(i=1;i<=n;i++)
  { l=1-l;
    for(j=0;j<=m;j++)
        { a[1-l][j]=a[l][j];
         //if(cost[i]>=j)
        a[1-l][j]=min(a[1-l][j],a[l][j-cost[i]]+energie[i]);
        }
  }
  g<<a[1-l][m];
    return 0;
}