#include<bits/stdc++.h>
using namespace std;
int n,k;
pair<int, int> a[1000];
int f[1000][110];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i].first>>a[i].second;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            f[i][j]=j+1;
            for(int p=1;p<i;p++){
                if(a[p].first<=a[i].first&&a[p].second<=a[i].second){
                    int d=a[i].first-a[p].first+a[i].second-a[p].second-1;
                    if(d<=j){
                        f[i][j]=max(f[i][j],f[p][j-d]+d+1);
                    }
                }
            }
        }

    }   
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,f[i][k]);
    }
    cout<<ans;
    return 0;
}