#include <fstream>
#define maxw 5006
using namespace std;

ifstream f("energii.in"); ofstream o("energii.out");
int a[1006][maxw],g,w;

void pd(int p,int x, int y,int&ct){
int i,d;
if (p==1) {
    for (i=1;i<=x;i++) a[p][i]=y;
    ct=x;
}
else {
    for (i=1;i<=x;i++) {if (a[p-1][i]) a[p][i]=min(a[p-1][i],y);
                        else a[p][i]=y; }
    d=a[p-1][x];
    ct += x;
    if (ct>w) ct=w;
    for (i=x+1;i<=ct;i++) if (a[p-1][i-1]){ if(a[p-1][i]) a[p][i]=min(a[p-1][i],a[p-1][i-1]+y);
                                            else a[p][i]=a[p-1][i-1]+y; }
                          else a[p][i]=d+y;
}

}

void citire(){
int i,x,y,r;
f>>g>>w;
r=0;
for (i=1;i<=g;i++){
    f>>x>>y;
    pd(i,x,y,r);
}
}

void afisare(){
o<<a[g][w];
}


int main(){
citire();
afisare();
return 0;
}