#include<bits/stdc++.h>

using namespace std;

int n,k,ans;

int c[1010][1010];

struct point{

int x,y;

}a[1010]; bool cmp(const point

&a,const point &b){

if(a.x!=b.x) return a.x<b.x;

return a.y<b.y;

} int main(){

cin>>n>>k;

for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;

sort(a+1,a+1+n,cmp);

for(int i=1;i<=n;i++){

for(int j=0;j<=k;j++){

c[i][j]=j+1;

for(int z=1;z<i;z++){

if(a[z].y>a[i].y)

continue;

int p=a[i].x-a[z].x+a[i].y-a[z].y-1;

if(j>=p) c[i][j]=max(c[i][j],c[z][j-p]+p+1); } } }

for(int i=1;i<=n;i++) ans=max(ans,c[i][k]); cout<<ans;

return 0;

}