The mayor of the Central Town wants to modernize Central Street, represented in this problem by the $(Ox)$ axis.

On this street, there are $n$ antennas, numbered from $1$ to $n$. The $i$-th antenna lies on the position $x_i$ and has an initial scope of $s_i$: it covers all integer positions inside the interval $[x_i - s_i; x_i + s_i]$.

It is possible to increment the scope of any antenna by $1$, this operation costs $1$ coin. We can do this operation as much as we want (multiple times on the same antenna if we want).

To modernize the street, we need to make all integer positions from $1$ to $m$ inclusive covered by at least one antenna. Note that it is authorized to cover positions outside $[1; m]$, even if it's not required.

What is the minimum amount of coins needed to achieve this modernization?


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n \le 80$ and $n \le m \le 100\ 000$).

The $i$-th of the next $n$ lines contains two integers $x_i$ and $s_i$ ($1 \le x_i \le m$ and $0 \le s_i \le m$).

On each position, there is at most one antenna (values $x_i$ are pairwise distinct).


-----Output-----

You have to output a single integer: the minimum amount of coins required to make all integer positions from $1$ to $m$ inclusive covered by at least one antenna.


-----Examples-----
Input
3 595
43 2
300 4
554 10

Output
281

Input
1 1
1 1

Output
0

Input
2 50
20 0
3 1

Output
30

Input
5 240
13 0
50 25
60 5
155 70
165 70

Output
26



-----Note-----

In the first example, here is a possible strategy:

  Increase the scope of the first antenna by $40$, so that it becomes $2 + 40 = 42$. This antenna will cover interval $[43 - 42; 43 + 42]$ which is $[1; 85]$  Increase the scope of the second antenna by $210$, so that it becomes $4 + 210 = 214$. This antenna will cover interval $[300 - 214; 300 + 214]$, which is $[86; 514]$  Increase the scope of the third antenna by $31$, so that it becomes $10 + 31 = 41$. This antenna will cover interval $[554 - 41; 554 + 41]$, which is $[513; 595]$ 

Total cost is $40 + 210 + 31 = 281$. We can prove that it's the minimum cost required to make all positions from $1$ to $595$ covered by at least one antenna.

Note that positions $513$ and $514$ are in this solution covered by two different antennas, but it's not important.

—

In the second example, the first antenna already covers an interval $[0; 2]$ so we have nothing to do.

Note that the only position that we needed to cover was position $1$; positions $0$ and $2$ are covered, but it's not important.

Difficulty: HARD
Tags: Dynamic programming

Sorting

Data structures

Greedy algorithms
Skill types: Dynamic programming

Sorting

Data structures

Greedy algorithms

Starter code:

Solutions:
3
import os
import sys

def main():
	(N, M) = read_ints()
	A = [tuple(read_ints()) for _ in range(N)]
	print(solve(N, M, A))

def solve(N, M, A):
	A.sort()
	D = {0: 0}
	for (x, s) in A:
		d = D.copy()
		for (x0, c) in d.items():
			if x - s <= x0 + 1:
				nx = x + s
				if nx not in D:
					D[nx] = c
				else:
					D[nx] = min(D[nx], c)
			else:
				nc = c + (x - s - x0 - 1)
				nx = x + s + nc - c
				if nx not in D:
					D[nx] = nc
				else:
					D[nx] = min(D[nx], nc)
	best = M * 2
	for (x, c) in D.items():
		if x == 0:
			continue
		if x < M:
			c += M - x
		best = min(best, c)
	return best
DEBUG = 'DEBUG' in os.environ

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

def read_int():
	return int(inp())

def read_ints():
	return [int(e) for e in inp().split()]

def dprint(*value, sep=' ', end='\n'):
	if DEBUG:
		print(*value, sep=sep, end=end)

def __starting_point():
	main()
__starting_point()


(n, m) = list(map(int, input().split()))
a = []
for i in range(n):
	(b, c) = list(map(int, input().split()))
	a.append((max(0, b - c), min(b + c, m)))
dp = [0] * (m + 1)
for i in range(1, m + 1):
	dp[i] = i
	for j in range(n):
		(c, d) = a[j]
		if c <= i and i <= d:
			dp[i] = dp[i - 1]
		elif i < c:
			cost = c - i
			dp[i] = min(dp[i], cost + dp[max(0, c - cost - 1)])
		elif i > d:
			cost = i - d
			dp[i] = min(dp[i], cost + dp[max(0, c - cost - 1)])
print(dp[m])


import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
A = []
COVERED = [0] * (m + 1)
for i in range(n):
	(x, y) = list(map(int, input().split()))
	A.append((x - y, x + y))
	for j in range(max(0, x - y), min(m + 1, x + y + 1)):
		COVERED[j] = 1
if min(COVERED[1:]) == 1:
	print(0)
	return
A.sort()
DP = [m] * (m + 2)
DP[1] = 0
covind = 1
while COVERED[covind] == 1:
	DP[covind] = 0
	covind += 1
DP[covind] = 0
NEXT = [i + 1 for i in range(m + 1)]
for j in range(m - 1, -1, -1):
	if COVERED[j + 1] == 1:
		NEXT[j] = NEXT[j + 1]

def nex(i):
	if i <= m:
		return NEXT[i]
	else:
		return m + 1
for i in range(1, m + 1):
	if COVERED[i] == 1:
		continue
	for (x, y) in A:
		if x < i:
			continue
		DP[nex(y + (x - i))] = min(DP[i] + (x - i), DP[nex(y + (x - i))])
ANS = DP[-1]
for i in range(m, -1, -1):
	if DP[i] != m + 1:
		ANS = min(ANS, DP[i] + (m + 1 - i))
print(ANS)


def dp(ind, max_covered):
	max_covered = min(m, max_covered)
	if ind not in cache:
		cache[ind] = {}
	d = cache[ind]
	if max_covered in d:
		return d[max_covered]
	ans = blah(ind, max_covered)
	d[max_covered] = ans
	return ans

class Node:

	def __init__(self, key, val, next=None):
		self.key = key
		self.val = val
		self.next = next

def blah(ind, max_covered):
	(x, s) = antenna[ind]
	if max_covered >= m:
		return 0
	if ind == len(antenna) - 1:
		if max_covered < x - s - 1:
			left_needed = x - s - (max_covered + 1)
			right_needed = max(m - (x + s), 0)
			ans = max(left_needed, right_needed)
			return ans
		else:
			right_boundary = max(max_covered, x + s)
			ans = max(0, m - right_boundary)
			return ans
	if max_covered < x - s - 1:
		num_needed = x - s - (max_covered + 1)
		new_boundary = min(x + s + num_needed, m)
		use_i = num_needed + dp(ind + 1, new_boundary)
		dont_use_i = dp(ind + 1, max_covered)
		return min(use_i, dont_use_i)
	else:
		new_boundary = min(max(max_covered, x + s), m)
		ans = dp(ind + 1, new_boundary)
		return ans
import sys
cache = {}
(n, m) = [int(x) for x in sys.stdin.readline().split(' ')]
antenna = []
for i in range(n):
	(x, s) = [int(x) for x in sys.stdin.readline().split(' ')]
	antenna.append((x, s))
antenna.sort(key=lambda a: a[0])
print(dp(0, 0))


import sys
from array import array
from typing import List, Tuple, TypeVar, Generic, Sequence, Union

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	(n, m) = map(int, input().split())
	a = sorted((tuple(map(int, input().split())) for _ in range(n)))
	dp = array('i', [10 ** 9]) * (m + 1)
	dp[0] = 0
	for (xi, si) in a:
		dp[min(xi + si, m)] = min(dp[min(xi + si, m)], dp[max(0, xi - si - 1)])
		for (i, delta) in zip(range(xi - si - 2, xi - si - m - 1, -1), range(2, m + 1)):
			dp[min(xi + si + delta - 1, m)] = min(dp[min(xi + si + delta - 1, m)], dp[i if i >= 0 else 0] + delta - 1)
		for i in range(m - 1, 0, -1):
			if dp[i] > dp[i + 1]:
				dp[i] = dp[i + 1]
	print(dp[-1])
main()


from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline

def factors(n):
	return sorted(list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))))

def li():
	return [int(i) for i in input().rstrip('\n').split(' ')]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n').split(' ')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
(n, m) = li()
l = []
for i in range(n):
	(x, y) = li()
	l.append([x - y, x + y])
dp = [m for i in range(m + 1)]
dp[0] = 0
for i in range(1, m + 1):
	dp[i] = min(dp[i - 1] + 1, dp[i])
	for j in l:
		x = max(0, j[0] - i)
		y = min(m, j[1] + x)
		dp[y] = min(dp[y], dp[i - 1] + x)
print(dp[-1])


import sys
from operator import itemgetter
input = sys.stdin.readline
(n, m) = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 9
new_info = []
for (pos, width) in info:
	tmp = [max(pos - width - 1, 0), min(pos + width, m)]
	new_info.append(tmp)
pos = 0
new_info = sorted(new_info, key=itemgetter(1))
dp = [[0] * (m + 2) for i in range(n + 1)]
for i in range(m + 2):
	dp[0][i] = i
for i in range(n):
	(begin, end) = new_info[i]
	for j in range(m + 2):
		if j <= end:
			dp[i + 1][j] = min(dp[i][begin], dp[i][j])
		else:
			dp[i + 1][j] = min(j - end + dp[i][max(begin - (j - end), 0)], dp[i][j])
print(dp[n][m])


import os
import sys

def solve(xs, m):
	xs = [(0, 0)] + xs
	dp = [0] * (m + 1)
	for i in range(1, m + 1):
		dp[i] = dp[i - 1] + 1
		for (idx, (x, s)) in enumerate(xs):
			if x - s <= i <= x + s:
				dp[i] = dp[i - 1]
				break
			if x + s < i:
				c = i - x - s
				dp[i] = min(c + dp[max(x - c - s - 1, 0)], dp[i])
	return dp[-1]

def pp(input):
	(n, m) = list(map(int, input().split()))
	xs = [tuple(map(int, input().split())) for _ in range(n)]
	print(solve(xs, m))
if 'paalto' in os.getcwd():
	from string_source import string_source
	pp(string_source('2 50\n20 0\n3 1\n'))
	pp(string_source('3 595\n43 2\n300 4\n554 10\n'))
	pp(string_source('1 1\n1 1\n'))
	pp(string_source('5 240\n13 0\n50 25\n60 5\n155 70\n165 70\n'))
else:
	pp(sys.stdin.readline)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
(n, m) = map(int, input().split())
antena = [list(map(int, input().split())) for i in range(n)]
DP = [float('inf')] * (m + 1)
DP[0] = 0
for i in range(1, m + 1):
	DP[i] = i
	for (x, s) in antena:
		l = max(1, x - s)
		r = min(m, x + s)
		if l <= i <= r:
			DP[i] = DP[i - 1]
			break
		elif r < i:
			cost = i - r
			DP[i] = min(DP[i], DP[max(0, l - cost - 1)] + cost)
print(DP[-1])


import sys
from bisect import bisect_right

def upgrade_minCost(n, m, antennas):
	covered = [False] * (m + 1)
	intervals = []
	for (x, s) in antennas:
		L = max(1, x - s)
		R = min(m, x + s)
		intervals.append((L, R))
		for i in range(L, R + 1):
			covered[i] = True
	intervals.sort()
	d = [m - i for i in range(m + 1)]
	for i in range(m - 1, -1, -1):
		if covered[i + 1]:
			d[i] = d[i + 1]
		else:
			ant_idx = bisect_right(intervals, (i, m))
			for (L, R) in intervals[ant_idx:]:
				u = L - i - 1
				prev = min(m, R + u)
				d[i] = min(d[i], u + d[prev])
	return d[0]

def main():
	reader = (map(int, s.split()) for s in sys.stdin)
	(n, m) = next(reader)
	antennas = [list(next(reader)) for _ in range(n)]
	ans = upgrade_minCost(n, m, antennas)
	print(ans)
main()


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
St = [list(map(int, input().split())) for _ in range(N)]
dp = [M - i for i in range(M + 1)]
for m in reversed(range(M)):
	covered = False
	for (x, s) in St:
		if x - s <= m + 1 <= x + s:
			covered = True
			break
		if m < x - s:
			u = x - s - m - 1
			dp[m] = min(dp[m], u + dp[min(M, x + s + u)])
	if covered:
		dp[m] = dp[m + 1]
print(dp[0])


(n, m) = [int(x.strip()) for x in input().split()]
u = [[int(x.strip()) for x in input().split()] for _ in range(n)]
u = [(max(x[0] - x[1], 1), min(x[0] + x[1], m)) for x in u]
u = sorted(u)
d = [2 ** 60] * (m + 11)
d[0] = 0
for (s, e) in u:
	next_d = [2 ** 60] * (m + 11)
	minv = min(d[max(0, s - 1):])
	expand = max((0, m - e, s - 1))
	for j in range(expand + 1):
		(st, ed) = (max(0, s - j - 1), min(m, e + j))
		minv = min(minv, d[st])
		next_d[ed] = min(next_d[ed], minv + j)
	minv = next_d[m]
	for j in range(m, 0, -1):
		minv = min(minv, next_d[j], d[j])
		d[j] = minv
print(d[m])


(n, m, l) = list(map(int, input().split(' '))) + [[]]
for i in range(n):
	l.append(list(map(int, input().split(' '))))
dp = [0] + [m for i in range(m)]
for i in range(1, m + 1):
	dp[i] = min(dp[i - 1] + 1, dp[i])
	for j in l:
		x = max(0, j[0] - j[1] - i)
		y = min(m, j[0] + j[1] + x)
		dp[y] = min(dp[y], dp[i - 1] + x)
print(dp[-1])


def readint():
	return int(input())

def readlistint():
	return list(map(int, input().split()))

def readgridint(rows):
	grid = []
	for idx in range(rows):
		col = list(map(int, input().split()))
		grid.append(col)
	return grid
antennas = []
total_len = -1
memo = {}

def solve(left, idx):
	if left > total_len:
		return 0
	key = (left, idx)
	if key in memo:
		return memo[key]
	if idx == len(antennas) - 1:
		ret = max(0, max(antennas[idx][0] - left, total_len - antennas[idx][1]))
		memo[key] = ret
		return ret
	else:
		best = solve(left, idx + 1)
		best = min(best, max(0, max(antennas[idx][0] - left, total_len - antennas[idx][1])))
		added = max(antennas[idx][0] - left, 0)
		best = min(best, added + solve(antennas[idx][1] + added + 1, idx + 1))
		memo[key] = best
		return best

def main():
	nonlocal total_len
	(N, L) = readlistint()
	total_len = L
	for idx in range(N):
		(pos, R) = readlistint()
		antennas.append([pos - R, pos + R])
	antennas.sort()
	INF = 100000000000
	dp = [INF] * (total_len + 10)
	dp[0] = 0
	for ant in antennas:
		(ant_left, ant_right) = ant
		for idx in range(0, total_len + 1):
			if dp[idx] == INF:
				continue
			dp[total_len] = min(dp[total_len], dp[idx] + max(0, max(ant_left - idx - 1, total_len - ant_right)))
			added = max(ant_left - idx - 1, 0)
			right_point = min(total_len, ant_right + added)
			dp[right_point] = min(dp[right_point], dp[idx] + added)
	print(dp[total_len])
main()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
dg = 10 ** 10
s = [0]
t = [0]
tank = []
for _ in [0] * n:
	(X, d) = map(int, input().split())
	tank.append((X + d) * dg + X)
tank.sort()
for e in tank:
	X_d = e // dg
	X = e % dg
	d = X_d - X
	s.append(max(1, X_d - d * 2))
	t.append(min(m, X_d))
n += 1
dp = [[0] * (m + 1) for i in range(2)]
for j in range(1, t[0] + 1):
	dp[0][j] = s[0] - 1
for j in range(t[0] + 1, m + 1):
	dp[0][j] = max(s[0] - 1, j - t[0])
for i in range(1, n):
	for j in range(1, m + 1):
		tmp = dp[(i + 1) % 2][j]
		if j <= t[i]:
			tmp = min(tmp, dp[(i + 1) % 2][s[i] - 1])
		else:
			tmp = min(tmp, dp[(i + 1) % 2][max(0, s[i] + t[i] - j - 1)] + j - t[i])
		dp[i % 2][j] = tmp
print(dp[(n + 1) % 2][-1])


A = []
(n, m) = map(int, input().split())
for i in range(1, n + 1):
	(x, s) = map(int, input().split())
	A.append((max(0, x - s), min(m, x + s)))
dp = [9999999] * (m + 1)
dp[0] = 0
for p in range(1, m + 1):
	for i in range(n):
		(a, b) = A[i]
		if p >= a and p <= b:
			dp[p] = dp[p - 1]
		elif p < a:
			pwr = a - p
			dp[p] = min(dp[p], pwr + dp[max(0, a - pwr - 1)], p)
		elif p > b:
			pwr = p - b
			dp[p] = min(dp[p], pwr + dp[max(a - pwr - 1, 0)], p)
print(dp[m])


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')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if not True else 1):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		(x, s) = map(int, input().split())
		a += [[max(0, x - s), min(m, x + s)]]
	dp = [m - i for i in range(m + 1)]
	dp[m] = 0
	for i in range(m - 1, -1, -1):
		for (alpha, omega) in a:
			if alpha <= i + 1 <= omega:
				dp[i] = min(dp[i], dp[i + 1])
			if i < alpha:
				p = alpha - i - 1
				dp[i] = min(dp[min(m, omega + p)] + p, dp[i])
	print(dp[0])


import sys
from operator import itemgetter
readline = sys.stdin.readline
(N, M) = map(int, readline().split())
inf = 10 ** 9 + 7
XS = [(0, 0)] + [tuple(map(int, readline().split())) for _ in range(N)]
XS.sort(key=lambda x: x[0] - x[1])
(x, s) = XS[0]
dp1 = [0] + [max(0, x - s - 1, j - x - s) for j in range(1, M + 2)]
for (x, s) in XS[1:]:
	dp1n = dp1[:]
	dp1n[min(M, x + s)] = min(dp1n[min(M, x + s)], dp1[max(0, x - s - 1)])
	for j in range(M):
		if x + s + j > M:
			break
		dp1n[x + s + j] = min(dp1n[x + s + j], j + dp1[max(0, x - s - 1 - j)])
	dp1 = dp1n[:]
	for i in range(M, -1, -1):
		dp1[i] = min(dp1[i], dp1[i + 1])
print(dp1[M])