Having written another programming contest, three Rabbits decided to grab some lunch. The coach gave the team exactly k time units for the lunch break.

The Rabbits have a list of n restaurants to lunch in: the i-th restaurant is characterized by two integers f_{i} and t_{i}. Value t_{i} shows the time the Rabbits need to lunch in the i-th restaurant. If time t_{i} exceeds the time k that the coach has given for the lunch break, then the Rabbits' joy from lunching in this restaurant will equal f_{i} - (t_{i} - k). Otherwise, the Rabbits get exactly f_{i} units of joy.

Your task is to find the value of the maximum joy the Rabbits can get from the lunch, depending on the restaurant. The Rabbits must choose exactly one restaurant to lunch in. Note that the joy value isn't necessarily a positive value. 


-----Input-----

The first line contains two space-separated integers — n (1 ≤ n ≤ 10^4) and k (1 ≤ k ≤ 10^9) — the number of restaurants in the Rabbits' list and the time the coach has given them to lunch, correspondingly. Each of the next n lines contains two space-separated integers — f_{i} (1 ≤ f_{i} ≤ 10^9) and t_{i} (1 ≤ t_{i} ≤ 10^9) — the characteristics of the i-th restaurant.


-----Output-----

In a single line print a single integer — the maximum joy value that the Rabbits will get from the lunch. 


-----Examples-----
Input
2 5
3 3
4 5

Output
4

Input
4 6
5 8
3 6
2 3
2 2

Output
3

Input
1 5
1 7

Output
-1

Difficulty: interview

Starter code:

Solutions:
import sys

(n, k) = [int(x) for x in sys.stdin.readline().strip().split()]

ans = -999999999999999999999999999999999999999999

for i in range(0, n):
    (f, t) = [int(x) for x in sys.stdin.readline().strip().split()]
    ans = max(ans, f-max(0,t-k))

print(ans)


I=lambda:list(map(int,input().split()))
n,k=I()
print(max((lambda a,b:a-max(0,b-k))(*I())for i in[0]*n))


import sys
my_file = sys.stdin
#my_file = open("input.txt", "r")
num = [int(i) for i in my_file.readline().strip("\n").split(" ")]
n = num[0]
k = num[1]
rest = []
max = -1000000000
for i in my_file.readlines():
    rest = [int(k) for k in i.strip("\n").split(" ")]
    if rest[0] > max:
        if rest[1] <= k:
            max = rest[0]
        elif rest[0]-(rest[1]-k) > max:
            max = rest[0]-(rest[1]-k)
print(max)

n,k=input().split()
n=int(n)
k=int(k)
ans=0
check =True
for i in range(n):
    f,t=input().split()
    f=int(f)
    t=int(t)
    if(t>k):
        j=f-(t-k)
    else:
        j=f
    if(j>ans or check):
        ans=j
        check=False
print(ans)


3

n, k = tuple(map(int, input().split()))
ft = [tuple(map(int, input().split())) for _ in range(n)]
print(max([f - t + k if t > k else f for f, t in ft]))


n, k = list(map(int,input().split()))
x = -100000000000000
for i in range(n):
    f, t = list(map(int,input().split()))
    if t > k: x = max(x, f + k - t)
    else: x = max(x, f)
print(x)


def value(t, f, k):
    if t > k:
        return (f - (t - k))
    else:
        return f


def main():
    first_line = input()
    first_line = first_line.split()
    
    n = int(first_line[0])
    k = int(first_line[1])

    t = []
    f = []
    for i in range(n):
        line = input()
        line = (line.split())
        f += [int(line[0])]
        t += [int(line[1])]

    maximum_index = 0
    maximum = -1 * float("inf")

    for i in range(0, n):
        val = value(t[i], f[i], k)
        if val > maximum:
            maximum = val
            maximum_index = val
            
    print(maximum)
    
        

    

import doctest
doctest.testmod()
main()   


n,k=list(map(int,input().split()))
ans=[]
for i in range(n):
    f,t=list(map(int,input().split()))
    if(t>k):
        ans.append(f-t+k)
    else:
        ans.append(f)
print(max(ans))


n,k=input().split()



f_arr=[]
t_arr=[]
for a in range (0,int(n)):
    f,t=input().split() 
    f_arr.append(int(f));t_arr.append(int(t))

##subs_arr=[]
##for l in range (0,int(n)):
##    if (t_arr[l]>int(k)):
##        subs_arr.append(t_arr[l])
##        
    


##for m in range (0,int(n)):
##    if (t_arr[m]<=int(k)):
##        print (max(f_arr))
##    if (t_arr[m]>int(k)):
##        print (max(subs_arr))

##for m in range (0,int(n)):
##    if (t_arr[m]<=int(k)):
##        
##        
##    if (t_arr[m]>int(k)):
##        z2=[]
##        z2.append(max(f_arr))
##        print (z2[0]) range

joy_arr=[]
for l in range (0,int(n)):
    if (t_arr[l]>int(k)):
        joy_arr.append(f_arr[l]-(t_arr[l]-int(k)))
    if (t_arr[l]<=int(k)):
        joy_arr.append(f_arr[l])


print(max(joy_arr))
        
    
    

    
    
    
    


        
    


n, k = list(map(int, input().split()))
a = -1<<30
for i in range(n):
    f, t = list(map(int, input().split()))
    if t > k: f -= t - k
    a = max(a, f)

print(a)



import sys

n_rest, time = tuple(int(x) for x in sys.stdin.readline().split())
max_joy = -100000000000000000000

for i in range(n_rest):
    f, t = tuple(int(x) for x in sys.stdin.readline().split())
    cur_joy = 0
    if t > time:
        cur_joy = f - (t - time)
    else:
        cur_joy = f
    max_joy = max(max_joy, cur_joy)

print(max_joy)


n,k = list(map(int, input().split()))
rest = []
for cont in range(0,n):
    l = list(map(int, input().split()))
    rest.append(l)

maxjoy = -9999999999999999
for r in rest:
    if r[1] > k:
        joy = r[0]-r[1] +k
    else:
        joy = r[0]
    if joy > maxjoy:
        maxjoy = joy
print(maxjoy)


n, k = list(map(int, input().split()))
f = [list(map(int, input().split())) for i in range(n)]

print(sorted(v[0] if v[1] <= k else v[0] - (v[1] - k) for v in f)[-1])


I = lambda: list(map(int, input().split()))
n, k = I()
f = [I() for i in range(n)]
print(max(v[0] if v[1] <= k else v[0] - (v[1] - k) for v in f))


def joy(f: int, t: int, k: int) -> int:
    return f - (t - k) if t > k else f


(n, k) = map(int, input().split())
joys = [0] * n

for i in range(n):
    (f, t) = map(int, input().split())
    joys[i] = joy(f, t, k)

print(max(joys))

n, k = map(int, input().split())
arr = [tuple(map(int, input().split())) for i in range(n)]
print(max([i[0] if k >= i[1] else i[0] - i[1] + k for i in arr]))

n, k = [int(i) for i in input().split()]
f = [0] * n
t = [0] * n
_max = -3 * (10 ** 9)
for i in range(0, n):
    f[i], t[i] = [int(i) for i in input().split()]
    _max = max(_max, (f[i]-(t[i]-k)) if t[i] > k else f[i])
print(_max)

n, k = map(int, input().split())
print (max([x[0] - max(0, x[1] - k) for x in [list(map(int, input().split())) for i in range(n)]]))

sa=input().split(' ')
rs=int(sa[0])
k=int(sa[1])
joy=-99999999999999999999999999999999999
for x in range(rs):
    sa2=input().split(' ')
    f_i=int(sa2[0])
    t_i=int(sa2[1])
    if t_i>k:
        joy=max(joy, f_i-(t_i-k))
    else:
        joy=max(joy, f_i)
print(joy)


def main():
    n, k = [int(i) for i in input().split()]
    
    result = -float("inf")
    for i in range(n):
        f, t = [int(i) for i in input().split()]
        result = max(result, f - max(0, t - k))
    
    print(result)

main()


n, k = (int(x) for x in input().split())
val = -10 ** 9
for i in range(n):
    f, t = (int(x) for x in input().split())
    cur = min(f, f - (t - k))
    if cur > val:
        val = cur
print(val)


import sys

n, k = [int(x) for x in (sys.stdin.readline()).split()]

ff, ft = [int(x) for x in (sys.stdin.readline()).split()]

h = 0
if(ft > k):
    h = ff - (ft - k)
else:
    h = ff
    
for i in range(n - 1):
    hh = 0
    f, t = [int(x) for x in (sys.stdin.readline()).split()]
    if(t > k):
        hh = f - (t - k)
    else:
        hh = f
    
    if(hh > h):
        h = hh
    
print(h)

n,k=map(int,input().split())

x,y=map(int,input().split())

kayf=x-max(0,y-k)

for i in range(1,n):
    x,y=map(int,input().split())
    da=x-max(0,y-k)
    if da>kayf:kayf=da

print(kayf)

n, k = [int(x) for x in input().split()]
ans = -10**15
for i in range(n):
	f, t = [int(x) for x in input().split()]
	ans = max(ans, f - max(0, t - k))
print(ans)


import math

def ost(a,b):
    if a%b!=0:
        return 1
    return 0

n,k=map(int,input().split())

ans=0
for i in range(n):
    f,t=map(int,input().split())
    tmp=0
    if t>k:
        tmp=f-(t-k)
    else:
        tmp=f
    if i>0:
        ans=max(tmp,ans)
    else:
        ans=tmp
print(ans)