#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
const int Mod = 1e9+7;
signed f[100005],sum[100005];
signed main(){
	f[0] = 1;
	cin>>n>>k;
	for(int i=1;i<=100000;i++){
		f[i] = f[i-1];
		if(i>=k)f[i]+=f[i-k];
		f[i]%=Mod;
		sum[i] = sum[i-1]+f[i];
		sum[i]%=Mod;
	}
	for(int i=1;i<=n;i++){
		int l,r;
		cin>>l>>r;
		cout<<(Mod+sum[r]-sum[l-1])%Mod<<endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 105,Mod=1e9+7;
#define int long long
int n,k,d;
int f[N][2];
signed main(){
	cin>>n>>k>>d;
	f[0][0] = 1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=min(i,k);j++){
			if(j<d){
				f[i][0]+=f[i-j][0];
				f[i][0]%=Mod;
			}
			f[i][1]+=f[i-j][1];
			f[i][1]%=Mod;
			if(j>=d){
				f[i][1] += f[i-j][0];
				f[i][1]%=Mod;
			}
		}
	}
	cout<<f[n][1]<<endl;
	return 0;
} 

#include <bits/stdc++.h>
using namespace std;
int n,a,b,c;
int f[4005];
int main(){
	cin>>n>>a>>b>>c;
	memset(f,-1,sizeof(f));
	f[0] = 0;
	for(int i=1;i<=n;i++){
		if(i>=a && f[i-a]!=-1)f[i] = max(f[i],f[i-a]+1);
		if(i>=b && f[i-b]!=-1)f[i] = max(f[i],f[i-b]+1);
		if(i>=c && f[i-c]!=-1)f[i] = max(f[i],f[i-c]+1);
		//cout<<i<<" "<<f[i]<<endl;
	}
	cout<<f[n]<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
//f[i]到坐标i最多能保留的信标数
//f[i] = f[i-1]
//f[i] = f[i-x]+1
int n,b[1000005],f[1000005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		b[x] = y;
	}
	int res = 0;
	for(int i=0;i<=1000000;i++){
		if(b[i]==0){
			f[i] = f[i-1];
		}
		else{
			if(b[i]>i)f[i] = 1;
			else f[i] = f[i-b[i]-1]+1;
		}
		res = max(res,f[i]);
	}
	cout<<n-res<<endl;
	return 0;
}