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: MEDIUM_HARD
Tags: Dynamic programming

Sorting
Skill types: Dynamic programming

Sorting

Starter code:

Solutions:
n = int(input())
x = [0] * (10 ** 6 + 1)
dp = [0] * (10 ** 6 + 1)
for i in range(n):
	(a, b) = map(int, input().split())
	x[a] = b
dp[0] = 1 if x[0] > 0 else 0
for i in range(1, 10 ** 6 + 1):
	if x[i] == 0:
		dp[i] = dp[i - 1]
	else:
		dp[i] = dp[i - x[i] - 1] + 1
print(n - max(dp))


n = int(input())
lighthouses = [0] * (1000000 + 2)
count = [0] * (1000000 + 2)
for i in range(n):
	(a, b) = map(int, input().split())
	lighthouses[a] = b
if lighthouses[0] > 0:
	count[0] = 1
for i in range(1, 1000000 + 1):
	if lighthouses[i] == 0:
		count[i] = count[i - 1]
	elif lighthouses[i] >= i:
		count[i] = 1
	else:
		count[i] = count[i - lighthouses[i] - 1] + 1
print(n - max(count))


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)


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)


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]
	elif d[i] >= i:
		Memo[i] = 1
	else:
		Memo[i] = Memo[i - d[i] - 1] + 1
	result = min(result, N - Memo[i])
print(result)


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 os
import sys
from io import BytesIO, IOBase
mod = 10 ** 9 + 7
from bisect import bisect_left as binary

def main():
	n = int(input())
	a = []
	d = dict()
	power = dict()
	for i in range(n):
		(x, y) = map(int, input().split())
		a.append(x)
		power[x] = y
	if n == 1:
		print(0)
		exit()
	a.sort()
	for (i, item) in enumerate(a):
		d[item] = i
	dp = [0] * (n + 1)
	dp[0] = 1
	dp[1] = 1
	z = [a[0]]
	mx = 0
	for i in range(1, n):
		temp = binary(z, a[i] - power[a[i]])
		dp[i] = dp[temp - 1] + 1
		z.append(a[i])
		mx = max(mx, dp[i])
	print(n - mx)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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
		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(n - max(dp))


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(-10000000.0)
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)


n = int(input())
pos = []
for i in range(n):
	pos.append(tuple(map(int, input().strip().split())))
nLine = {}
maxi = max(pos)[0]
for i in pos:
	nLine[i[0]] = i[1]
temp = [0 for i in range(maxi + 1)]
pins = []
no = 0
for i in range(maxi, -1, -1):
	if i in nLine:
		no += 1
		pins.append(i)
	temp[i] = no
noKills = [0 for i in range(n)]
for i in range(n - 1, -1, -1):
	upto = max(pins[n - 1 - i] - nLine[pins[n - 1 - i]], 0)
	noKills[i] = temp[upto] - temp[pins[n - 1 - i]]
dp = [0 for i in range(n)]
for i in range(n):
	prev = i - noKills[i] - 1
	if prev < 0:
		prev = 0
	dp[i] = noKills[i] + dp[prev]
mini = dp[-1]
for i in range(n - 1, -1, -1):
	mini = min(dp[i] + n - 1 - i, mini)
print(mini)


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))


import sys
input = sys.stdin.readline
from bisect import *
n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n)]
ab.sort(key=lambda k: k[0])
a = [-10 ** 18] + [ai for (ai, _) in ab]
dp = [0] * (n + 1)
for i in range(1, n + 1):
	j = bisect_left(a, ab[i - 1][0] - ab[i - 1][1]) - 1
	dp[i] = dp[j] + i - j - 1
ans = 10 ** 18
for i in range(n + 1):
	ans = min(ans, dp[i] + n - i)
print(ans)


n = int(input())
bb = [0] * 1000001
for _ in range(n):
	(a, b) = 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))


import bisect
from math import inf
a = []
b = []
maxi = 10 ** 6
ind = [-1] * (maxi + 1)
n = int(input())
for _ in range(n):
	(x, y) = map(int, input().split())
	a.append([x, y])
	b.append(x)
a.sort()
b.sort()
for i in range(len(b)):
	ind[b[i]] = i
dp = [0] * n
dp[0] = 0
for i in range(1, len(a)):
	curr_pos = a[i][0]
	dest = curr_pos - a[i][1]
	ans = bisect.bisect_left(b, dest) - 1
	if ans < 0:
		dp[i] = ind[curr_pos]
	else:
		dp[i] = dp[ans] + ind[curr_pos] - ans - 1
mini = inf
for i in range(len(dp)):
	mini = min(mini, dp[i] + len(dp) - i - 1)
print(mini)


import bisect
import collections
import copy
import functools
import heapq
import itertools
import math
import sys
import string
sys.setrecursionlimit(99999)
n = int(input())
ps = []
for _ in range(n):
	(pos, power) = map(int, input().split())
	ps.append([pos, power])
ps.sort()
pp = []
dp = [0] * n
for (i, (pos, power)) in enumerate(ps):
	j = bisect.bisect_left(pp, pos - power)
	if j == 0:
		dp[i] = 1
	else:
		dp[i] = 1 + dp[j - 1]
	pp.append(pos)
print(n - max(dp))


def bisect_left(A, ele):
	l = 0
	r = len(A) - 1
	while r > l:
		mid = (l + r) // 2
		if A[mid][0] >= ele:
			r = mid
		else:
			l = mid + 1
	return r

def answer(n, A):
	A.sort(key=lambda x: x[0])
	dp = [0] * n
	for i in range(1, n):
		ele = A[i][0] - A[i][1]
		index = bisect_left(A, ele)
		if index == 0:
			dp[i] = i
		else:
			dp[i] = i - index + dp[index - 1]
	mini = dp[-1]
	for i in range(n - 1, 0, -1):
		mini = min(mini, n - i + dp[i - 1])
	return min(mini, n)
n = int(input())
arr = []
for i in range(n):
	(l, p) = map(int, input().split())
	arr.append([l, p])
print(answer(n, arr))


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()
for i in range(1, len(dptable)):
	delupto = a[i] - b[i]
	delupto = bisect.bisect_left(a, delupto)
	dptable[i] = dptable[delupto - 1] + 1
print(n - max(dptable))


n = int(input())
li = [[]]
l = [-1] * 1000001
maxi = 0
for i in range(0, n):
	li = list(map(int, input().split()))
	l[li[0]] = li[1]
	if li[0] > maxi:
		maxi = li[0]
k = 0
a = [0] * (maxi + 1)
for i in range(0, maxi + 1):
	if l[i] == -1:
		a[i] = k
		continue
	if i - l[i] < 1:
		a[i] = 1
		k = 1
	else:
		a[i] = a[i - l[i] - 1] + 1
		k = a[i]
print(n - max(a[0:maxi + 1]))


from bisect import bisect_left
n = int(input())
a = sorted([[int(i) for i in input().split()] for _ in range(n)])
(a, b) = ([i[0] for i in a], [i[1] for i in a])
pref = [0]
for i in range(n):
	x = bisect_left(a, a[i] - b[i])
	pref.append(pref[x] + i - x)
ans = 100000.0 + 5
for i in range(n + 1):
	ans = min(ans, i + pref[n - i])
print(ans)


from bisect import bisect_left, bisect_right
n = int(input())
positon = []
poser = []
for i in range(n):
	(x, u) = map(int, input().split())
	poser.append([x, u])
	positon.append(x)
poser.sort()
positon.sort()
dp = [0 for i in range(n)]
for i in range(0, n):
	value = bisect_left(positon, poser[i][0] - poser[i][1]) - 1
	dp[i] = dp[value] + 1
print(n - max(dp))


import bisect
n = int(input())
data = []
for _ in range(n):
	data.append(list(map(int, input().split())))
data.sort(key=lambda x: x[0])
a = [x[0] for x in data]
b = [x[1] for x in data]
dp = [0] * n
dp[0] = 1
for i in range(1, n):
	ind = bisect.bisect_left(a, a[i] - b[i], 0, i)
	if ind > 0:
		dp[i] = dp[ind - 1] + 1
	else:
		dp[i] = 1
print(n - max(dp))


import bisect
n = int(input())
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
a = [ab[i][0] for i in range(n)]
b = [ab[i][1] for i in range(n)]
dp = [0] * n
for i in range(n):
	left = a[i] - b[i]
	idx = bisect.bisect_left(a, left)
	if idx == 0:
		dp[i] = i
	else:
		dp[i] = dp[idx - 1] + (i - idx)
ans = n
for i in range(n):
	ans = min(ans, dp[i] + (n - 1 - 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()


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))


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
import io, os
import math
from heapq import *
gcd = math.gcd
sqrt = math.sqrt
ceil = math.ceil
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def print(x, end='\n'):
	sys.stdout.write(str(x) + end)

def strinp(testcases):
	k = 5
	if testcases == -1 or testcases == 1:
		k = 1
	f = str(input())
	f = f[2:len(f) - k]
	return f

def ind(ch):
	return ord(ch) - ord('a')

def binsearch(arr, v):
	pos = 0
	last = len(arr) - 1
	i = last
	while i > 0:
		while last >= pos + i and v >= arr[pos + i]:
			pos = pos + i
		i = i // 2
	return pos

def main():
	n = int(input())
	pos = [0] * n
	mi = 10 ** 9
	for i in range(n):
		pos[i] = list(map(int, input().split()))
		mi = min(mi, pos[i][0])
	if n == 1:
		print(0)
		sys.exit()
	pos.sort()
	por = [0] * n
	for i in range(n):
		por[i] = pos[i][1]
		pos[i] = pos[i][0]
	dp = [0] * n
	for i in range(n):
		f = pos[i] - por[i] - 1
		if f < mi:
			dp[i] = 1
		else:
			k = binsearch(pos, f)
			dp[i] = 1 + dp[k]
	print(n - max(dp))
main()


from sys import stdin
from collections import defaultdict

def solve():
	n = int(stdin.readline())
	energy = defaultdict(int)
	maxn = 0
	for i in range(n):
		(a, b) = tuple(map(int, stdin.readline().split(' ')))
		maxn = max(maxn, a)
		energy[a] = b
	ans = 0
	table = [0] * (maxn + 1)
	table[0] = int(energy[0] > 0)
	for i in range(maxn + 1):
		if energy[i] == 0:
			table[i] = table[i - 1]
		elif energy[i] < i:
			table[i] = table[i - 1 - energy[i]] + 1
		else:
			table[i] = 1
		ans = max(ans, table[i])
	print(n - ans)
solve()


import sys, os, io
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
Neo = lambda : list(map(int, input().split()))
(test,) = Neo()
n = test
a = sorted([Neo() for _ in range(n)])
(a, b) = ([i[0] for i in a], [i[1] for i in a])
pref = [0]
for i in range(n):
	x = bisect.bisect_left(a, a[i] - b[i])
	pref.append(pref[x] + i - x)
ans = 100000.0 + 5
for i in range(n + 1):
	ans = min(ans, i + pref[n - i])
print(ans)


class CodeforcesTask607ASolution:

	def __init__(self):
		self.result = ''
		self.beacons_count = 0
		self.beacons = [0 for x in range(1000005)]

	def read_input(self):
		self.beacons_count = int(input())
		for x in range(self.beacons_count):
			a_b = [int(x) for x in input().split(' ')]
			self.beacons[a_b[0]] = a_b[1]

	def process_task(self):
		dp = [0 for x in range(1000005)]
		for x in range(len(self.beacons)):
			if self.beacons[x]:
				dp[x] = 1
		mx = 0
		for x in range(1, 1000005):
			if not self.beacons[x]:
				dp[x] = dp[x - 1]
			elif self.beacons[x] >= x:
				dp[x] = 1
			else:
				dp[x] = dp[x - self.beacons[x] - 1] + 1
			if dp[x] > mx:
				mx = dp[x]
		self.result = str(self.beacons_count - mx)

	def get_result(self):
		return self.result
Solution = CodeforcesTask607ASolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


n = int(input())
lis = [0] * (1000000 + 2)
dp = [0] * (1000000 + 2)
for i in range(n):
	(a, b) = map(int, input().split())
	lis[a] = b
if lis[0] > 0:
	dp[0] = 1
for i in range(1, 1000000 + 1):
	if lis[i] == 0:
		dp[i] = dp[i - 1]
	elif lis[i] >= i:
		dp[i] = 1
	else:
		dp[i] = dp[i - lis[i] - 1] + 1
print(n - max(dp))


import sys, os, io
from sys import stdin
from bisect import bisect_left, bisect_right

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = ii()
l = []
for i in range(n):
	l.append(tuple(li()))
l.sort()
DP = [0] * n
for i in range(n):
	x = bisect_left(l, (l[i][0] - l[i][1], 0))
	if x == 0:
		DP[i] = 1
	else:
		DP[i] = DP[x - 1] + 1
print(n - max(DP))


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
import math

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
no = 'NO'
yes = 'YES'

def solve():
	n = ii()
	a = []
	b = []
	l = []
	for i in range(n):
		(x, y) = li()
		l.append([x, y])
	l.sort()
	for i in range(n):
		a.append(l[i][0])
		b.append(l[i][1])
	DP = [0] * n
	for i in range(n):
		x = bisect_left(a, a[i] - b[i])
		if x == 0:
			DP[i] = 1
		else:
			DP[i] = DP[x - 1] + 1
	print(n - max(DP))
t = 1
for _ in range(t):
	solve()


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))


from sys import stdin
input = stdin.readline
n = int(input())
a = []
for _ in range(n):
	(aa, bb) = [int(x) for x in input().split()]
	aa -= 1
	a.append((aa, bb))
a.sort()
(a, b) = zip(*a)
dp = []
for i in range(n):
	v = a[i] - b[i]
	if v <= a[0]:
		dp.append(i)
		continue
	r = i
	l = 0
	while l < r:
		m = l + (r - l) // 2
		if a[m] == v:
			break
		if a[m] > v:
			r = m
		else:
			l = m + 1
	m = l + (r - l) // 2
	dp.append(i - m + dp[m - 1])
z = [dp[i] + (n - 1 - i) for i in range(n)]
ans = min(z)
print(ans)


n = int(input())
a = []
b = []
d = {}
for i in range(n):
	(x, y) = map(int, input().split())
	d[x] = y
	a.append(x)
	b.append(y)
m = max(a)
ans = [0] * (m + 1)
for i in range(m + 1):
	if d.get(i, -1) == -1:
		ans[i] = ans[i - 1]
	else:
		ans[i] = 1 + (ans[i - d[i] - 1] if i - d[i] - 1 >= 0 else 0)
t = max(ans)
print(n - t)


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)))
n = int(input())
beacons = []
for _ in range(n):
	(a, b) = map(int, input().split())
	beacons.append((a, b))
print(min_destroyed(beacons))


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):
	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 = []
NUM = []
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))


n = int(input())
maxn = 1000000.0 + 5
mx = 0
b = [0] * int(maxn)
for i in range(n):
	(a1, b1) = map(int, input().split())
	b[a1] = b1
dp = [0] * int(maxn)
if b[0] > 0:
	dp[0] = 1
for i in range(1, int(maxn)):
	if b[i] == 0:
		dp[i] = dp[i - 1]
	elif b[i] >= i:
		dp[i] = 1
	else:
		dp[i] = dp[i - b[i] - 1] + 1
	mx = max(mx, dp[i])
print(n - mx)


n = int(input())
lis = [0] * (1000000 + 2)
dp = [0] * (1000000 + 2)
t = c = s = lef = 0
for i in range(n):
	(a, b) = map(int, input().split())
	lis[a] = b
if lis[0] > 0:
	dp[0] = 1
for i in range(1, 1000000 + 1):
	if lis[i] == 0:
		dp[i] = dp[i - 1]
	elif lis[i] >= i:
		dp[i] = 1
	else:
		dp[i] = dp[i - lis[i] - 1] + 1
print(n - max(dp))


def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) // 2)
		if arr[m] > k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
n = int(input())
ls = []
for i in range(n):
	(a, b) = map(int, input().split())
	ls.append([a, b])
ls.sort()
arr = [ls[0][0]]
dp = [0 for i in range(n + 1)]
for i in range(1, n):
	k = countGreater(arr, len(arr), ls[i][0] - ls[i][1] - 1)
	dp[i + 1] = k + dp[i - k]
	arr.append(ls[i][0])
ans = n
for i in range(1, n + 1):
	ans = min(ans, dp[i] + n - i)
print(ans)


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
n = Int()
power = {}
for i in range(n):
	(p, po) = value()
	power[p] = po
points = sorted(power.keys())
destroyed = defaultdict(int)
for i in range(len(points)):
	pos = bisect_left(points, points[i] - power[points[i]])
	destroyed[points[i]] = i - pos
	if pos != 0:
		destroyed[points[i]] += destroyed[points[pos - 1]]
print(min((n - 1 - i + destroyed[points[i]] for i in range(len(points)))))


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)


mod = 10 ** 6 + 1
b = [0] * mod
dp = [0] * mod
maxi = 0
n = int(input())
for _ in range(n):
	(a, po) = map(int, input().split())
	b[a] = po
if b[0] > 0:
	dp[0] = 1
for i in range(1, mod):
	if b[i] == 0:
		dp[i] = dp[i - 1]
	elif b[i] >= i:
		dp[i] = 1
	else:
		dp[i] = dp[i - b[i] - 1] + 1
	maxi = max(maxi, dp[i])
print(n - maxi)


n = int(input())
a = [0] * (10 ** 6 + 5)
dp = [0] * (10 ** 6 + 5)
maxx = -1
for i in range(n):
	(b, c) = map(int, input().split())
	a[b] = c
for i in range(len(a)):
	if i == 0:
		if a[0] > 0:
			dp[0] = 1
	elif a[i] == 0:
		dp[i] = dp[i - 1]
	elif a[i] >= i:
		dp[i] = 1
	else:
		dp[i] = dp[i - a[i] - 1] + 1
	if dp[i] > maxx:
		maxx = dp[i]
print(n - maxx)


from bisect import bisect_left
n = int(input())
arr = [list(map(int, input().split())) for j in range(n)]
arr.sort()
pos = [i[0] for i in arr]
pre = [0]
for i in range(1, n):
	ind = bisect_left(pos, arr[i][0] - arr[i][1])
	pre.append(i - ind + pre[max(0, ind - 1)])
ans = pre[-1]
d = 0
for i in range(n - 1, 0, -1):
	d += 1
	ans = min(ans, d + pre[i - 1])
print(ans)


n = int(input())
(dp, li, ans) = ([0] * 1000010, [0] * 1000010, 0)
for i in range(n):
	(a, b) = map(int, input().split())
	li[a] = b
for i in range(1000010):
	if li[i]:
		dp[i] = dp[i - li[i] - 1] + 1
	else:
		dp[i] = dp[i - 1]
	ans = max(ans, dp[i])
print(n - ans)


from sys import stdin
item = lambda : stdin.readline().split()
n = int(stdin.readline())
(lst, d) = ([], {})
for _ in range(n):
	(a, b) = map(int, item())
	d[a] = b
	lst.append(a)
lst.sort()
res = [0] * n
from bisect import bisect_left as bis
for (i, x) in enumerate(lst):
	elem = bis(lst, x - d[x]) - 1
	if elem == -1:
		res[i] = i
		continue
	res[i] = res[elem] + i - elem - 1
for (i, x) in enumerate(lst):
	res[i] += n - 1 - i
print(min(res))


n = int(input())
lis = [0] * 1000004
dp = [0] * 1000004
for i in range(n):
	(a, b) = map(int, input().split())
	lis[a] = b
if lis[0] > 0:
	dp[0] = 1
for i in range(1, 1000002):
	if lis[i] > 0:
		dp[i] = dp[max(-1, i - lis[i] - 1)] + 1
	else:
		dp[i] = dp[i - 1]
print(n - max(dp))


from bisect import bisect_left as bl
n = int(input())
l = []
for i in range(n):
	l.append(tuple(list(map(int, input().split()))))
l.sort()
DP = [0] * n
for i in range(n):
	x = bl(l, (l[i][0] - l[i][1], 0))
	DP[i] = 1
	if x > 0:
		DP[i] = DP[x - 1] + 1
print(n - max(DP))


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()


n = int(input())
b = []
for i in range(n):
	b.append(list(map(int, input().split())))
b.sort()
D = [0] * n
D[0] = 0

def binSearch(target, data, init_end):
	start = 0
	end = init_end
	while start <= end:
		mid = (start + end) // 2
		if data[mid][0] == target:
			return mid
		elif data[mid][0] < target:
			start = mid + 1
		else:
			end = mid - 1
	if data[mid][0] < target:
		return mid + 1
	else:
		return mid
for i in range(1, n):
	result = binSearch(b[i][0] - b[i][1], b, i)
	dead = i - result
	if result == 0:
		D[i] = dead
	else:
		D[i] = D[result - 1] + dead
ans_list = []
ans_list.append(len(D))
for i in range(n + 1):
	ans_list.append(D[len(D) - i - 1] + i)
print(min(ans_list))


n = int(input())
powers = sorted([tuple(map(int, input().split())) for _ in range(n)])

def find_smaller_than_in_asc_sorted(x, l, s, e):
	if s == e or l[s] > x:
		return (None, None)
	if l[e - 1] < x:
		return (l[e - 1], e - 1)
	if e - s == 1:
		if l[s] < x:
			return (l[s], s)
		else:
			return (None, None)
	sep = (s + e) // 2
	sample = l[sep]
	if sample < x:
		return find_smaller_than_in_asc_sorted(x, l, sep, e)
	elif sample == x:
		return (l[sep - 1], sep - 1)
	else:
		return find_smaller_than_in_asc_sorted(x, l, s, sep)
distructions = [0] * len(powers)
for (index, (pos, power)) in enumerate(powers):
	distruction = 0
	(_, next_index) = find_smaller_than_in_asc_sorted((pos - power, 0), powers, 0, index)
	if next_index is not None:
		distruction += index - next_index - 1 + distructions[next_index]
	else:
		distruction += index
	distructions[index] = distruction
for i in range(len(powers)):
	distructions[i] += len(powers) - i - 1
print(min(distructions))


from bisect import *
a = int(input())
pos = []
ans = []
for i in range(a):
	(x, y) = map(int, input().split())
	ans.append([x, y])
	pos.append(x)
ans.sort()
pos.sort()
from collections import *
al = defaultdict(int)
al[0] = 0
dp = [a - 1]
for i in range(1, len(pos)):
	r = bisect_left(pos, pos[i] - ans[i][1])
	c1 = 1
	r -= 1
	if r < 0:
		dp.append(len(pos) - 1)
		al[i] = i
	else:
		cost = len(pos) - i - 1 + (i - r - 1) + al[r]
		dp.append(cost)
		al[i] = i - r - 1 + al[r]
print(min(dp))


import bisect
n = int(input())
b = []
p = []
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
a.sort()
for i in range(n):
	b.append(a[i][0])
	p.append(a[i][1])
dp = [0] * n
for i in range(n):
	j = bisect.bisect_left(b, b[i] - p[i])
	dp[i] = i - j + dp[j - 1]
ans = 10 ** 9
c = 1
for j in range(n - 1, -1, -1):
	ans = min(ans, dp[j - 1] + c, dp[j] + c - 1)
	c = c + 1
print(ans)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
INF = 999999999999999999999999
alphabets = 'abcdefghijklmnopqrstuvwxyz'

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class SegTree:

	def __init__(self, n):
		self.N = 1 << n.bit_length()
		self.tree = [0] * (self.N << 1)

	def update(self, i, j, v):
		i += self.N
		j += self.N
		while i <= j:
			if i % 2 == 1:
				self.tree[i] += v
			if j % 2 == 0:
				self.tree[j] += v
			(i, j) = (i + 1 >> 1, j - 1 >> 1)

	def query(self, i):
		v = 0
		i += self.N
		while i > 0:
			v += self.tree[i]
			i >>= 1
		return v

def SieveOfEratosthenes(limit):
	isPrime = [True] * (limit + 1)
	isPrime[0] = isPrime[1] = False
	primes = []
	for i in range(2, limit + 1):
		if not isPrime[i]:
			continue
		primes += [i]
		for j in range(i * i, limit + 1, i):
			isPrime[j] = False
	return primes

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		n = ri()
		beacon = []
		a = []
		for i in range(n):
			(x, y) = ria()
			a.append(x)
			beacon.append([x, y])
		a = sorted(a)
		beacon = sorted(beacon)
		dp = [n + 1] * (n + 1)
		dp[0] = 0
		ans = dp[0] + (n - 1)
		for i in range(1, n):
			pos = beacon[i][0] - beacon[i][1]
			ind = bisect.bisect_left(a, pos) - 1
			if ind >= 0:
				dp[i] = dp[ind] + i - ind - 1
			else:
				dp[i] = i
			ans = min(ans, dp[i] + (n - (i + 1)))
		wi(ans)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


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


import bisect

def main():
	n = int(input())
	beacons = []
	coords = []
	for i in range(n):
		(a, b) = map(int, input().split())
		beacons.append((a, b))
		coords.append(a)
	if n == 1:
		print(0)
		return
	coords.sort()
	beacons.sort()
	dp = [0] * n
	min_val = float('inf')
	for i in range(1, n):
		(a, b) = beacons[i]
		x_left = a - b - 1
		index = bisect.bisect(coords, x_left)
		if index - 1 >= 0:
			dp[i] = dp[index - 1] + i - index
		else:
			dp[i] = i
		min_val = min(min_val, dp[i] + n - i - 1)
	print(min_val)
main()


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 os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
	(a[i], b[i]) = map(int, input().split())

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z
b = sort_list(b, a)
a.sort()
t = 0
dp = [0] * (max(a) + 1)
for i in range(max(a) + 1):
	if i == a[t]:
		if i - b[t] - 1 < 0:
			dp[i] = 1
		else:
			dp[i] = dp[i - b[t] - 1] + 1
		t += 1
	else:
		dp[i] = dp[i - 1]
print(n - max(dp))


import os
import sys
from io import BytesIO, IOBase

def main():
	maxn = int(1000000.0 + 5)
	d = [0] * maxn
	n = int(input())
	for _ in range(n):
		(a, b) = map(int, input().split())
		d[a] = b
	for i in range(maxn):
		if d[i] >= i and d[i] > 0:
			d[i] = 1
		elif d[i] > 0:
			d[i] = d[i - d[i] - 1] + 1
		else:
			d[i] = d[i - 1]
	print(n - max(d))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
import math
import collections
from pprint import pprint
mod = 1000000007

def vector(size, val=0):
	vec = [val for i in range(size)]
	return vec

def matrix(rowNum, colNum, val=0):
	mat = []
	for i in range(rowNum):
		collumn = [val for j in range(colNum)]
		mat.append(collumn)
	return mat

def fun(i, a):
	(l, h) = (0, i - 1)
	ans = -1
	while l <= h:
		m = (l + h) // 2
		if a[m][0] >= a[i][0] - a[i][1]:
			(ans, h) = (m, m - 1)
		else:
			l = m + 1
	if ans == -1:
		return 0
	return i - ans
n = int(input())
a = matrix(n, 2)
for i in range(n):
	(a[i][0], a[i][1]) = map(int, input().split())
a.sort()
dp = matrix(n, 2)
dp[0][1] = 1
for i in range(1, n):
	cnt = fun(i, a)
	dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])
	dp[i][1] = dp[i - cnt - 1][1] + 1
print(n - max(dp[n - 1][0], dp[n - 1][1]))


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections as col

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def solve():
	N = getInt()
	beacons = []
	for n in range(N):
		(A, B) = getInts()
		beacons.append((A, B))
	beacons.sort()
	dp = [0]
	for j in range(1, N):
		rng = beacons[j][0] - beacons[j][1]
		if beacons[j - 1][0] < rng:
			dp.append(dp[-1])
			continue
		if beacons[0][0] >= rng:
			dp.append(j)
			continue
		right = j - 1
		left = 0
		while right - left > 1:
			middle = (left + right) // 2
			if beacons[middle][0] >= rng:
				right = middle
			else:
				left = middle
		tmp = dp[left] + j - left - 1
		dp.append(tmp)
	ans = 10 ** 9
	for j in range(N):
		ans = min(ans, dp[j] + N - j - 1)
	return ans
print(solve())


import sys
input = sys.stdin.buffer.readline

def solution():
	n = int(input())
	a = [0] * (2 * 10 ** 6)
	dp = [0] * (2 * 10 ** 6)
	for i in range(n):
		(x, y) = map(int, input().split())
		a[x] = y
	if a[0] > 0:
		dp[0] = 1
	for i in range(1, len(dp)):
		if a[i] == 0:
			dp[i] = dp[i - 1]
		elif i <= a[i]:
			dp[i] = 1
		else:
			dp[i] = dp[i - a[i] - 1] + 1
	print(n - max(dp))
solution()


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 bisect import bisect_left as lower

def put():
	return map(int, input().split())
n = int(input())
(x, p, y) = ([], [], [])
for i in range(n):
	(a, b) = put()
	y.append((-a, b))
y.sort()
for i in range(n):
	(a, b) = y[i]
	x.append(a)
	p.append(b)
dp = [0] * n
ans = int(1000000000.0)
for i in range(n - 1, -1, -1):
	j = lower(x, x[i] + p[i] + 1)
	if j == n:
		dp[i] = n - 1 - i
	else:
		dp[i] = j - i - 1 + dp[j]
ans = dp[0]
for i in range(n - 1):
	ans = min(ans, dp[i + 1] + i + 1)
print(ans)