#include <bits/stdc++.h>
using namespace std;
vector <pair<int,int> > v; // vector to stor pairs of position,power
int n;
int dest [100010]; /* dest[i] stores the number of beacons destroyed if all
beacons upto i+1 had been destroyed by additional beacon */
bool cmp(pair<int,int> l, pair <int,int> r)
{
return(l.first< r.first);
}
int bsearch(int k)
{
int low = 0;
int high = k;
int mid = high;
while(low<=high)
{
mid = (low+high)/2;
int gap = v[k].first - v[mid].first;
if(gap < v[k].second)
high = mid-1;
if(gap > v[k].second)
low = mid+1;
if(gap == v[k].second)
{
break;
}
}
return mid;
}
inline void activate(int k)
{
/* do a binary search to get the max number beacons destroyed.
If still beacons are left, we activate the beacon and add its already
calculated destroy count to current beacon
*/
int pwreach = bsearch(k);
dest[k] = k-pwreach;
if(pwreach>0)
dest[k] += dest[pwreach-1];
}
int main()
{
ios_base::sync_with_stdio(false);
cin >> n;
int pos,pwr;
for(int i = 0; i < n ; ++i)
{
cin >> pos >>pwr;
v.push_back(make_pair(pos,pwr));
}
sort(v.begin(),v.end(),cmp);
for(int i = 1; i < n; ++i)
{
/* Activation of the 0th (array index) beacon will destroy none. So we
begin by activating the first beacon*/
activate(i);
}
int mdest = dest[n-1];
for(int i = n-2;i >=0; --i)
{
/* we begin from the end, assuming all beacons upto i+1 had been
destroyed */
if((dest[i] + n-i-1) < mdest)
mdest = dest[i]+n-i-1;
}
cout << mdest << "\n";
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp2ZWN0b3IgPHBhaXI8aW50LGludD4gPiB2OyAvLyB2ZWN0b3IgdG8gc3RvciBwYWlycyBvZiBwb3NpdGlvbixwb3dlcgppbnQgbjsKCmludCBkZXN0IFsxMDAwMTBdOyAvKiBkZXN0W2ldIHN0b3JlcyB0aGUgbnVtYmVyIG9mIGJlYWNvbnMgZGVzdHJveWVkIGlmIGFsbAoJCQkJCWJlYWNvbnMgdXB0byBpKzEgaGFkIGJlZW4gZGVzdHJveWVkIGJ5IGFkZGl0aW9uYWwgYmVhY29uICovCgpib29sIGNtcChwYWlyPGludCxpbnQ+IGwsIHBhaXIgPGludCxpbnQ+IHIpCnsKCXJldHVybihsLmZpcnN0PCByLmZpcnN0KTsKfQppbnQgYnNlYXJjaChpbnQgaykKewoJaW50IGxvdyA9IDA7CglpbnQgaGlnaCA9IGs7CglpbnQgbWlkID0gaGlnaDsKCXdoaWxlKGxvdzw9aGlnaCkKCXsKCQltaWQgPSAobG93K2hpZ2gpLzI7CgkJaW50IGdhcCA9IHZba10uZmlyc3QgLSB2W21pZF0uZmlyc3Q7CgkJaWYoZ2FwIDwgdltrXS5zZWNvbmQpCgkJCWhpZ2ggPSBtaWQtMTsKCQlpZihnYXAgPiB2W2tdLnNlY29uZCkKCQkJbG93ID0gbWlkKzE7CgkJaWYoZ2FwID09IHZba10uc2Vjb25kKQoJCXsKCQkJYnJlYWs7CgkJfQoJfQoJcmV0dXJuIG1pZDsKfQoKaW5saW5lIHZvaWQgYWN0aXZhdGUoaW50IGspCnsJCgkvKiBkbyBhIGJpbmFyeSBzZWFyY2ggdG8gZ2V0IHRoZSBtYXggbnVtYmVyIGJlYWNvbnMgZGVzdHJveWVkLgoJSWYgc3RpbGwgYmVhY29ucyBhcmUgbGVmdCwgd2UgYWN0aXZhdGUgdGhlIGJlYWNvbiBhbmQgYWRkIGl0cyBhbHJlYWR5IAoJY2FsY3VsYXRlZCBkZXN0cm95IGNvdW50IHRvIGN1cnJlbnQgYmVhY29uCgkqLyAKCWludCBwd3JlYWNoID0gYnNlYXJjaChrKTsKCWRlc3Rba10gPSBrLXB3cmVhY2g7CglpZihwd3JlYWNoPjApCgkJZGVzdFtrXSArPSBkZXN0W3B3cmVhY2gtMV07Cn0KCmludCBtYWluKCkKewoJaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CgljaW4gPj4gbjsJCglpbnQgcG9zLHB3cjsKCWZvcihpbnQgaSA9IDA7IGkgPCBuIDsgKytpKQoJewoJCWNpbiA+PiBwb3MgPj5wd3I7CgkgICAgdi5wdXNoX2JhY2sobWFrZV9wYWlyKHBvcyxwd3IpKTsJCgl9Cglzb3J0KHYuYmVnaW4oKSx2LmVuZCgpLGNtcCk7CgoJZm9yKGludCBpID0gMTsgaSA8IG47ICsraSkKCXsKCQkvKiBBY3RpdmF0aW9uIG9mIHRoZSAwdGggKGFycmF5IGluZGV4KSBiZWFjb24gd2lsbCBkZXN0cm95IG5vbmUuIFNvIHdlIAoJCWJlZ2luIGJ5IGFjdGl2YXRpbmcgdGhlIGZpcnN0IGJlYWNvbiovCgkJYWN0aXZhdGUoaSk7Cgl9CglpbnQgbWRlc3QgPSBkZXN0W24tMV07Cglmb3IoaW50IGkgPSBuLTI7aSA+PTA7IC0taSkKCXsKCQkvKiB3ZSBiZWdpbiBmcm9tIHRoZSBlbmQsIGFzc3VtaW5nIGFsbCBiZWFjb25zIHVwdG8gaSsxIGhhZCBiZWVuIAoJCWRlc3Ryb3llZCAqLwoJCWlmKChkZXN0W2ldICsgbi1pLTEpIDwgbWRlc3QpCgkJCW1kZXN0ID0gZGVzdFtpXStuLWktMTsKCX0KCWNvdXQgPDwgbWRlc3QgPDwgIlxuIjsKCXJldHVybiAwOwp9