There are n beacons located at distinct positions on a number line. The i-th beacon has position a_{i} and power level b_{i}. When the i-th beacon is activated, it destroys all beacons to its left (direction of decreasing coordinates) within distance b_{i} inclusive. The beacon itself is not destroyed however. Saitama will activate the beacons one at a time from right to left. If a beacon is destroyed, it cannot be activated.

Saitama wants Genos to add a beacon strictly to the right of all the existing beacons, with any position and any power level, such that the least possible number of beacons are destroyed. Note that Genos's placement of the beacon means it will be the first beacon activated. Help Genos by finding the minimum number of beacons that could be destroyed.


-----Input-----

The first line of input contains a single integer n (1 ≤ n ≤ 100 000) — the initial number of beacons.

The i-th of next n lines contains two integers a_{i} and b_{i} (0 ≤ a_{i} ≤ 1 000 000, 1 ≤ b_{i} ≤ 1 000 000) — the position and power level of the i-th beacon respectively. No two beacons will have the same position, so a_{i} ≠ a_{j} if i ≠ j.


-----Output-----

Print a single integer — the minimum number of beacons that could be destroyed if exactly one beacon is added.


-----Examples-----
Input
4
1 9
3 1
6 1
7 4

Output
1

Input
7
1 1
2 1
3 1
4 1
5 1
6 1
7 1

Output
3



-----Note-----

For the first sample case, the minimum number of beacons destroyed is 1. One way to achieve this is to place a beacon at position 9 with power level 2.

For the second sample case, the minimum number of beacons destroyed is 3. One way to achieve this is to place a beacon at position 1337 with power level 42.

Difficulty: competition

Starter code:

Solutions:
n = int(input())
pos_blast = [list(map(int, input().split())) for _ in range(n)]
MAX_N = max(pos_blast, key=lambda x: x[0])[0] + 2
power = [0 for _ in range(MAX_N)]
tower = [False for _ in range(MAX_N)]
can_destroy = [0 for _ in range(MAX_N)]
for pos, blast in pos_blast:
    pos += 1
    tower[pos] = True
    power[pos] = blast
for i in range(1, MAX_N):
    if not tower[i]:
        can_destroy[i] = can_destroy[i-1]
    else:
        can_destroy[i] = can_destroy[max(0, i - power[i] - 1)] + 1
print(n - max(can_destroy))


import sys
N = 1<<20
ar = [0]*N

dp = [0]*N
n = int(input())
for i in range(0, n):
    inp = input().split()
    ar[int(inp[0])+1]= int(inp[1])
for i in range(N):
    dp[i] = (1 if ar[i]>=i else dp[i-ar[i]-1]+1) if ar[i] else dp[i-1]
print(n-max(dp))


import sys
N = 1<<20
ar = [0]*N
n = int(input())
for i in range(0, n):
    inp = input().split()
    ar[int(inp[0])+1]= int(inp[1])
for i in range(N):
    ar[i] = (1 if ar[i]>=i else ar[i-ar[i]-1]+1) if ar[i] else ar[i-1]
print(n-max(ar))


n = int(input())
Becone = [list(map(int, input().split())) for i in range(n) ]
Becone.sort( key = lambda x : x[0])
dp = [0]*1000001
#for i in range(1000001) :
#    dp[i] = 0

if Becone[0][0] == 0 :
    dp[0] = 1
    Becone.pop(0)

ans = n - dp[0]
for i in range(1, 1000001) :
    if not Becone :
        break
    if i != Becone[0][0] :
        dp[i] = dp[i-1]
        continue

    a,b = Becone.pop(0)
    if a-b <= 0 :
        dp[i] = 1
    else :
        dp[i] = dp[i-b-1]+1

    ans = min( ans, n - dp[i] )

print( ans )


from array import *

n = int(input())
Becone = [list(map(int, input().split())) for i in range(n) ]
Becone.sort( key = lambda x : x[0])
dp = array('i', [0]*1000001)

if Becone[0][0] == 0 :
    dp[0] = 1
    Becone.pop(0)

ans = n - dp[0]
for i in range(1, 1000001) :
    if not Becone :
        break
    if i != Becone[0][0] :
        dp[i] = dp[i-1]
        continue

    a,b = Becone.pop(0)
    if a-b <= 0 :
        dp[i] = 1
    else :
        dp[i] = dp[i-b-1]+1

    ans = min( ans, n - dp[i] )

print( ans )


from sys import stdin

n = int(stdin.readline())
Becone = [list(map(int, stdin.readline().split())) for i in range(n) ]
Becone.sort( key = lambda x : x[0])
dp = [0]*1000001

if Becone[0][0] == 0 :
    dp[0] = 1
    Becone.pop(0)

ans = n - dp[0]
for i in range(1, 1000001) :
    if not Becone :
        break
    if i != Becone[0][0] :
        dp[i] = dp[i-1]
        continue

    a,b = Becone.pop(0)
    if a-b <= 0 :
        dp[i] = 1
    else :
        dp[i] = dp[i-b-1]+1

    ans = min( ans, n - dp[i] )

print( ans )


def main():
    n = int(input())
    bb = [0] * 1000001
    for _ in range(n):
        a, b = list(map(int, input().split()))
        bb[a] = b
    a = 0
    for i, b in enumerate(bb):
        if b:
            a = (bb[i - b - 1] + 1) if i > b else 1
        bb[i] = a
    print(n - max(bb))


def __starting_point():
    main()

__starting_point()

n = int(input())
dp = [0] * 1000007
majak = [0] * 1000007

q = 1000007
p = 0
for i in range(n):
    a, b = map(int, input().split())
    q = min(q, a)
    majak[a] = b

dp[q] = 1
ma = 1
for i in range(q + 1, 1000003, 1):
    if(majak[i] == 0):
        dp[i] = dp[i - 1]
    else:
        dp[i] = dp[i - majak[i] - 1] + 1
        ma = max(ma, dp[i])

print(n - ma)

dp = []
def fun(n, a):
	dp[0] = 1
	for i in range(1, n):
		l, r = 0, i - 1
		while l <= r:
			m = (l + r)>>1
			if a[i][0] - a[m][0] <= a[i][1]:
				r = m - 1
			else:
				l = m + 1
		#print (i, x)
		dp[i] = dp[r] + 1




n = int(input())
dp = [0 for i in range(n)]
a=[]
for i in range(n):
	l = list(map(int, input().split()))
	a.append(l)
a.sort()
power = [0 for i in range(n)]

fun(n, a)
#print (dp)
print(n - max(dp))	


import bisect

def __starting_point():
    n = int(input())
    beacon = [tuple(map(int, input().split())) for _ in range(n)]
    beacon.sort()
    
    destroyed = [0]*n
    for i in range(n):
        lo = beacon[i][0] - beacon[i][1]
        pos = bisect.bisect_left(beacon, (lo, -1), hi=i-1)
        if beacon[pos][0] >= lo:
            pos -= 1
        if pos < 0:
            destroyed[i] = i
        else:
            destroyed[i] = max(0, i - pos - 1 + destroyed[pos])
    
    best = n
    for i, v in enumerate(destroyed):
        best = min(best, v + n - i - 1)
    print(best)
__starting_point()

import sys

MAX_X = 1000 * 1000 + 10

def main():
    n = int(sys.stdin.readline())

    arr = [0] * MAX_X
    cnt = [0] * MAX_X
    dp = [0] * MAX_X
    for i in range(n):
        x, c = list(map(int, sys.stdin.readline().split()))
        arr[x + 1] = c

    for i in range(1, MAX_X):
        cnt[i] += cnt[i - 1] + (arr[i] != 0)
    
    for i in range(1, MAX_X):
        dp[i] = dp[max(0, i - arr[i] - 1)] + cnt[i - 1] - cnt[max(0, i - arr[i] - 1)]

    answer = dp[MAX_X - 1]
    add = 0

    for i in range(MAX_X - 1, -1, -1):
        answer = min(answer, add + dp[i])
        add += (arr[i] != 0)

    sys.stdout.write(str(answer))

main()


read = lambda: list(map(int, input().split()))
n = int(input())
p = sorted([tuple(read()) for i in range(n)])
a = [0] * (n + 1)
b = [0] * (n + 1)
for i in range(1, n + 1):
    a[i], b[i] = p[i - 1]
a[0] = int(-1e7)
dp = [0] * (n + 1)
for i in range(1, n + 1):
    L = 0
    R = n + 1
    while R - L > 1:
        M = (L + R) // 2
        if a[i] - b[i] <= a[M]: R = M
        else: L = M
    dp[i] = dp[L] + 1
ans = n - max(dp)
print(ans)


import bisect


def min_destroyed(beacons):
    beacons.sort()
    dest = []
    for i, (a, b) in enumerate(beacons):
        pos = bisect.bisect_left(beacons, (a-b, 0), hi=i)
        if pos == 0:
            dest.append(i)
        else:
            dest.append(dest[pos-1] + i-pos)

    n = len(beacons)
    return min(d + (n-i-1) for i, d in enumerate(dest))


def __starting_point():
    n = int(input())
    beacons = []
    for _ in range(n):
        a, b = list(map(int, input().split()))
        beacons.append((a, b))
    print(min_destroyed(beacons))

__starting_point()

n = int(input())
a = [0]*1000001
b = [0]*1000001
for i in range(n):
  l = list(map(int,input().split()))
  a[l[0]] = 1
  b[l[0]] = l[1]
  
notdestroyed = [0]*1000001
if a[0] == 1:
  notdestroyed[0] = 1
for i in range(1,1000001):
  if a[i] == 1:
    notdestroyed[i] = notdestroyed[i-b[i]-1]+1
  else:
    notdestroyed[i] = notdestroyed[i-1]
    
print(n-max(notdestroyed))

n = int(input())
lista = []
for i in range(n):
    lista.append([int(x) for x in input().split()])
lista.sort()

diccionario = dict()
nada = True
last = 0
maximo = 0
for x, i in lista:
    if nada == True:
        for c in range(0, x):
            diccionario[c] = 0
        diccionario[x] = 1
        maximo = 1
        nada = False
        last = x
    else:
        for w in range(last, x):
            diccionario[w] = diccionario[last]
        if i >= x:
            diccionario[x] = 1
        else:
            aux = diccionario[x - i - 1] + 1
            if aux > maximo:
                maximo = aux
            diccionario[x] = aux
        last = x
print(n - maximo)


N = int(input())
d = [0 for i in range(1000005)]
Memo = [0 for i in range(1000005)]
max_pos = 0
for i in range(N):
    subList = input().split()
    index = int(subList[0])
    d[index] = int(subList[1])
    max_pos = max(index, max_pos)
if (d[0] != 0):
    Memo[0] = 1

result = N
result = min(result, N-Memo[0])

for i in range(1, max_pos+1):
    if d[i] == 0:
        Memo[i] = Memo[i-1]
    else:
        if d[i] >= i:
            Memo[i] = 1
        else:
            Memo[i] = Memo[i-d[i]-1]+1
    result = min(result, N-Memo[i])
print(result)


N = int(input())
d = [0 for i in range(1000001)]
Memo = [0 for i in range(1000001)]
max_pos = 0
for i in range(N):
    subList = input().split()
    index = int(subList[0])
    d[index] = int(subList[1])
    max_pos = max(index, max_pos)
if (d[0] != 0):
    Memo[0] = 1

result = N
result = min(result, N-Memo[0])

for i in range(1, max_pos+1):
    if d[i] == 0:
        Memo[i] = Memo[i-1]
    else:
        if d[i] >= i:
            Memo[i] = 1
        else:
            Memo[i] = Memo[i-d[i]-1]+1
    result = min(result, N-Memo[i])
print(result)


from bisect import bisect_left, bisect_right
from collections import Counter
from collections import deque
from itertools import accumulate

import math

R = lambda: map(int, input().split())
n = int(input())
a, dp = sorted([tuple(R()) for _ in range(n)]), [0] * n
for i, (loc, dis) in enumerate(a):
    dp[i] = dp[bisect_left(a, (loc - dis, -10**10)) - 1] + 1
print(n - max(dp))

n = int(input())

dp = [0] * 1000007

majak = [0] * 1000007



q = 1000007

p = 0

for i in range(n):

    a, b = list(map(int, input().split()))

    q = min(q, a)

    majak[a] = b



dp[q] = 1

ma = 1

for i in range(q + 1, 1000003, 1):

    if(majak[i] == 0):

        dp[i] = dp[i - 1]

    else:

        dp[i] = dp[i - majak[i] - 1] + 1

        ma = max(ma, dp[i])



print(n - ma)



# Made By Mostafa_Khaled


import sys,bisect
n=int(input())
a,b=[],[]
for _ in range(n):
	ai,bi=list(map(int,input().split(' ')))
	a.append(ai)
	b.append(bi)

dptable=[1 for i in range(n+1)]
dptable[0]=0
a.insert(0,-1*sys.maxsize)
b.insert(0,0)
ab=list(zip(a,b))
sorted(ab)
b=[x for _,x in sorted(zip(a,b))]
a.sort()
#print(a,"\n",b)
for i in range(1,len(dptable)):
	delupto=a[i]-b[i]
	delupto=bisect.bisect_left(a,delupto)
	#print(delupto,i)
	dptable[i]=dptable[delupto-1]+1
print(n-max(dptable))


import bisect
class b:
	def __init__(self, loc, val, ls):
		self.loc = loc
		self.val = val
		self.ls = ls
		self.done = False
		self.ans = -1

	def do(self):
		if self.done: return self.ans
		x = bisect.bisect_left(self.ls, self.loc-self.val) - 1
		if x == -1: self.ans = 0
		else:
			self.ans = ls[x].do() + 1
		self.done =True
		return self.ans

	def __lt__(self, obj):
		if type(obj) == int: return obj > self.loc
		return obj.loc > self.loc

ls = []
for _ in range(int(input())):
	x,y = map(int, input().split(" "))
	ls.append(b(x, y, ls))
ls.sort()
m = -1
for l in ls:
	m = max(m, l.do())
print(len(ls) - (m+1))

n = int(input())
bb = [0] * 1000001
for _ in range(n):
    a, b = list(map(int, input().split()))
    bb[a] = b
a = 0
for i, b in enumerate(bb):
    if b:
        if i>b :
            a = (bb[i - b - 1] + 1)
        else :
            a=1
            
         
    bb[i] = a
print(n - max(bb))


def bin(mas,x):
    l = 0
    r = len(mas)
    while (r > l + 1):
        m = (r + l) // 2;
        if (x < mas[m]):
            r = m;
        else:
            l = m
    return l

n = int(input())
a = [-9999999]
b = [9999999]
dp = [0] * (n + 1)
for i in range(n):
    x,y=[int(i) for i in input().split()]
    a.append(x)
    b.append(y)

a, b = (list(x) for x in zip(*sorted(zip(a, b))))



for i in range(1,n+1):
    z = a[i] - b[i] - 1
    x = bin(a, z)
    dp[i] = dp[x] + ( i - x - 1)
ans = 10**30
for i in range(1, n + 1):
    ans = min(ans, dp[i] + n - i)
print(ans)

from operator import itemgetter
n = int(input())
abi = [[-10**9,0]] + [list(map(int,input().split())) for i in range(n)]
abi.sort(key = itemgetter(0))
ar = [0] * (n+1)
ar[0] = 0
def check(pos,num):
    #print(pos,num)
    if abi[pos][0] < num:
        return True
    else:
        return False
def binsearch(num):
    high = n+1
    low = 0
    mid = (high + low) // 2
    while high >= low:
        if check(mid,num):
            low = mid + 1
        else:
            high = mid - 1
        mid = (high + low) // 2
    return mid
ans = n
for i in range(1,n+1):
    num = binsearch(abi[i][0] - abi[i][1])
    ar[i] = i - num - 1+ ar[num]
    ans = min(ans, ar[i] + n - i)
print(ans)


def bsearch(arr,num,start,end):
    mid=int((start+end)/2)
    if start>end:
        return (start,0)
    if arr[mid]==num:
        return (mid,1)
    elif arr[mid]<num:
        return bsearch(arr,num,mid+1,end)
    else:
        return bsearch(arr,num,start,mid-1)
t=int(input())
A=[]
B=[]
N=[]#next undestroyed beacon
NUM=[]#number of destroyed beacon if current veacon activated

abp=[]
for i in range(0,t):
    ab=input().split(' ')
    a,b=int(ab[0]),int(ab[1])
    abp.append((a,b))
abp_S=sorted(abp,key = lambda bk:bk[0])
for i in range(0,len(abp_S)):
    a,b=abp_S[i]
    A.append(a)
    B.append(b)
    pos=bsearch(A,a-b,0,len(A)-1) 
    if pos[0]==0:
        N.append(pos[0]-1)
        NUM.append(i)
    else:
        N.append(pos[0]-1)
        NUM.append((i-pos[0])+NUM[pos[0]-1])
damages=[]
for i in range(0,len(A)):
    damages.append((len(A)-(i+1))+NUM[i])
print(min(damages))