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: interview

Starter code:

Solutions:
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))])

#print(DP)
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)

        
        
    


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

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:
        #dprint(x, s)
        #dprint(D)
        d = D.copy()
        for x0, c in d.items():
            if x - s <= x0 + 1:
                nx = x + s
                #dprint('  ', nx, '=>', c, '(x0=', x0, 'c=', c, ')')
                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
                #dprint('  ', nx, '=>', nc, '(x0=', x0, 'c=', c, ')')
                if nx not in D:
                    D[nx] = nc
                else:
                    D[nx] = min(D[nx], nc)
        #dprint(D)

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

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

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

# Antennas coverage

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():
    # inf = open('input.txt', 'r')
    # reader = (map(int, line.split()) for line in inf)
    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)
    
    # inf.close()

def __starting_point():
    main()
__starting_point()

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


# path = {}

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]
	# key = (ind, max_covered)

	if max_covered >= m:
		# path[key] = Node(key, 0)
		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)
			# path[key] = Node(key, ans)
			return ans
		else:
			right_boundary = max(max_covered, x + s)
			ans = max(0, m - right_boundary)
			# path[key] = Node(key, ans)
			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)

		# if use_i < dont_use_i:
		# 	path[key] = Node(key, num_needed, path[(ind + 1, new_boundary)])
		# else:
		# 	path[key] = Node(key, 0, path[(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)
		# path[key] = Node(key, 0, path[(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))


     
A = [(0, 0)]
inf = 999999999999
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 = [inf] * (m+1)
dp[0] = 0
A = sorted(A)
 
for p in range(1, m+1):    
    for i in range(1, n+1):
 
        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])

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

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

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

# M = mod = 10**9 + 7
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 inv_mod(n):return pow(n, mod - 2, mod)
 
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])

n, m = list(map(int,input().split(' ')))
l = []
for i in range(n):
    x, y = list(map(int,input().split(' ')))
    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])

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]))
    #print(left, idx, ret)
    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()
  #print(total_len, antennas)
  #ret = solve(1, 0)
  #print(ret)
  
  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()

#watu
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])

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
20 0
3 1
"""
        )
    )

    pp(
        string_source(
            """3 595
43 2
300 4
554 10
"""
        )
    )

    pp(
        string_source(
            """1 1
1 1
"""
        )
    )

    pp(
        string_source(
            """5 240
13 0
50 25
60 5
155 70
165 70
"""
        )
    )

else:
    pp(sys.stdin.readline)