#include <fstream>
#include <cstring>
#define DIM 1005
using namespace std;

ifstream fin("copaci2.in");
ofstream fout("copaci2.out");
int C[DIM],P[DIM],H[DIM],S[DIM],N,K,sol,hmax,D[DIM],v[DIM],a[DIM];
int abs(int x){
    if(x<0)
        return -x;
    return x;
}
int verif(int x){
    memset(P,0,sizeof(P));
    memset(v,0,sizeof(v));
    for(int i=2;i<=N;i++){
        int p=1,u=0;
        for(int j=0;j<=hmax;j++){
            C[j]=0x3f3f3f3f;
            C[j]=min(C[j],v[min(j+x,hmax)]+abs(H[i]-j)*S[i]);
            while(p<=u && C[j]<C[D[u]])
                u--;
            D[++u]=j;
            if(j-D[p]>2*x)
                p++;
            a[j]=C[D[p]];
        }
        memcpy(v,a,sizeof(a));
        memcpy(P,C,sizeof(C));
    }
    for(int i=0;i<=hmax;i++)
        if(C[i]<=K)
            return 1;
    return 0;
}
int main(){
    fin>>N>>K;
    for(int i=1;i<=N;i++){
        fin>>H[i]>>S[i];
        hmax=max(hmax,H[i]);
    }
    int p=1;
    int u=1000;
    while(p<=u){
        int mid=(p+u)>>1;
        if(verif(mid)){
            sol=mid;
            u=mid-1;
        }
        else
            p=mid+1;
    }
    fout<<sol<<"\n";
    fin.close();fout.close();
    return 0;
}