Kefa wants to celebrate his first big salary by going to restaurant. However, he needs company. 

Kefa has n friends, each friend will agree to go to the restaurant if Kefa asks. Each friend is characterized by the amount of money he has and the friendship factor in respect to Kefa. The parrot doesn't want any friend to feel poor compared to somebody else in the company (Kefa doesn't count). A friend feels poor if in the company there is someone who has at least d units of money more than he does. Also, Kefa wants the total friendship factor of the members of the company to be maximum. Help him invite an optimal company!


-----Input-----

The first line of the input contains two space-separated integers, n and d (1 ≤ n ≤ 10^5, $1 \leq d \leq 10^{9}$) — the number of Kefa's friends and the minimum difference between the amount of money in order to feel poor, respectively.

Next n lines contain the descriptions of Kefa's friends, the (i + 1)-th line contains the description of the i-th friend of type m_{i}, s_{i} (0 ≤ m_{i}, s_{i} ≤ 10^9) — the amount of money and the friendship factor, respectively. 


-----Output-----

Print the maximum total friendship factir that can be reached.


-----Examples-----
Input
4 5
75 5
0 100
150 20
75 1

Output
100

Input
5 100
0 7
11 32
99 10
46 8
87 54

Output
111



-----Note-----

In the first sample test the most profitable strategy is to form a company from only the second friend. At all other variants the total degree of friendship will be worse.

In the second sample test we can take all the friends.

Difficulty: interview

Starter code:

Solutions:
from collections import namedtuple
from operator    import itemgetter

Friend = namedtuple("Friend", "m s")

n, d = list(map(int, input().split()))
f = [ ]
for i in range(n):
    f.append(Friend(*list(map(int, input().split()))))
f.sort(key=itemgetter(0))
left = 0
cur = f[0].s
result = cur
for i, fr in enumerate(f[1:], 1):
    while left < i and f[left].m + d <= fr.m:
        cur -= f[left].s
        left += 1
    cur += fr.s
    result = max(result, cur)
print(result)


n, d = list(map(int, input().split()))

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

v = sorted(v)


lo = 0
totalFriendship = v[0][1]
bestFriendship = totalFriendship

for i in range(1, n):
    while v[i][0] - v[lo][0] >= d:
        totalFriendship -= v[lo][1]
        lo += 1
    totalFriendship += v[i][1]

    bestFriendship = max(bestFriendship, totalFriendship)

print(bestFriendship)



n,d=map(int,input().split())
t=[]
for i in range(n):
	x,y=map(int,input().split())
	t+=[(x,y)]
t=sorted(t, key=lambda colonnes: colonnes[0])
i=0
j=1
(q,r)=t[0]
vTemp=r
rTemp=r
qtemp=q
v=vTemp
while j<n:
	(x,y)=t[j]
	if x>=q+d:
		vTemp-=rTemp
		i+=1
		(q,r)=t[i]
		qTemp=q
		rTemp=r
	else:
		vTemp+=y
		v=max(v,vTemp)
		j+=1
print(v)

n, d = list(map(int, input().split()))
a = sorted([list(map(int, input().split())) for i in range(n)])
left = 0
cur_sum = 0
max_sum = 0
for right in range(n):
    cur_sum += a[right][1]
    while a[right][0] - a[left][0] >= d:
        cur_sum -= a[left][1]
        left += 1
    if cur_sum > max_sum:
        max_sum = cur_sum
print(max_sum)
    


3
# -*- coding: <utf-8> -*-

import itertools as ittls
from collections import Counter

def sqr(x):
    return x*x

def inputarray(func = int):
    return list(map(func, input().split()))

# -------------------------------
# -------------------------------

N, d = list(map(int, input().split()))

A = [(None, None)]*N
for i in range(N):
    A[i] = tuple(map(int, input().split()))

A.sort(key=lambda x: x[0])
prefix = [0] + [None]*len(A)
for i, (money, friendship) in enumerate(A):
    prefix[i + 1] = prefix[i] + friendship

res, i, j = 0, 0, 0
while i < len(A):
    while j < len(A) and A[j][0] < A[i][0] + d:
        j = j + 1

    if prefix[j] - prefix[i] > res:
        res = prefix[j] - prefix[i]

    i = i + 1

print(res)


def main(n, d):
    p = []
    for i in range(n):
        a, b = list(map(int, input().split()))
        p.append([a, b])
    p.sort()
    maxi = 0
    sum = 0
    e = []
    g = 0
    em = 0
    while len(p) != 0:
        while g != n and p[g][0] < p[em][0] + d:
            sum += p[g][1]
            g += 1
        if g == n:
            maxi = max(maxi, sum)
            print(max(maxi, sum))
            break
        else:
            maxi = max(maxi, sum)
            while em != g and p[em][0] + d <= p[g][0]:
                sum -= p[em][1]
                em += 1
n, d = list(map(int, input().split()))
main(n, d)
    
    


#!/usr/bin/env python
# 580B_company.py - Codeforces.com/problemset/problem/580/B by Sergey 2015

import unittest
import sys

###############################################################################
# Company Class (Main Program)
###############################################################################


class Company:
    """ Company representation """

    def __init__(self, test_inputs=None):
        """ Default constructor """

        it = iter(test_inputs.split("\n")) if test_inputs else None

        def uinput():
            return next(it) if it else sys.stdin.readline().rstrip()

        # Reading single elements
        [self.n, self.d] = list(map(int, uinput().split()))

        # Reading multiple lines of pairs
        pairs = (" ".join(uinput() for i in range(self.n))).split()
        self.numa = [int(pairs[i]) for i in range(0, 2*self.n, 2)]
        self.numb = [int(pairs[i]) for i in range(1, 2*self.n, 2)]

        self.money = [(self.numa[i], self.numb[i]) for i in range(self.n)]
        self.money = sorted(self.money)

        self.partsum = [0]
        sum = 0
        for i in range(self.n):
            sum += self.money[i][1]
            self.partsum.append(sum)

    def calculate(self):
        """ Main calcualtion function of the class """

        result = 0

        for i in range(self.n):
            mlb = self.money[i][0]
            mrb = mlb + self.d
            ilb = i
            irb = lbound(self.money, mrb)
            sumf = self.partsum[irb] - self.partsum[ilb]
            result = max(result, sumf)

        return str(result)


def lbound(v, n):
    b = 0
    e = len(v)
    while b != e:
        mid = (b + e) // 2
        if v[mid][0] < n:
            b = mid + 1
        else:
            e = mid
    return b

###############################################################################
# Unit Tests
###############################################################################


class unitTests(unittest.TestCase):

    def test_single_test(self):
        """ Company class testing """

        # Constructor test
        test = "4 5\n75 5\n0 100\n150 20\n75 1"
        d = Company(test)
        self.assertEqual(d.n, 4)
        self.assertEqual(d.d, 5)
        self.assertEqual(d.numa, [75, 0, 150, 75])
        self.assertEqual(d.numb, [5, 100, 20, 1])

        # Sample test
        self.assertEqual(Company(test).calculate(), "100")

        # Sample test
        test = "5 100\n0 7\n11 32\n99 10\n46 8\n87 54"
        self.assertEqual(Company(test).calculate(), "111")

        # Sample test
        test = ""
        # self.assertEqual(Company(test).calculate(), "0")

        # My tests
        test = ""
        # self.assertEqual(Company(test).calculate(), "0")

        # Time limit test
        # self.time_limit_test(5000)

    def time_limit_test(self, nmax):
        """ Timelimit testing """
        import random
        import timeit

        # Random inputs
        test = str(nmax) + " " + str(nmax) + "\n"
        numnums = [str(i) + " " + str(i+1) for i in range(nmax)]
        test += "\n".join(numnums) + "\n"
        nums = [random.randint(1, 10000) for i in range(nmax)]
        test += " ".join(map(str, nums)) + "\n"

        # Run the test
        start = timeit.default_timer()
        d = Company(test)
        calc = timeit.default_timer()
        d.calculate()
        stop = timeit.default_timer()
        print(("\nTimelimit Test: " +
              "{0:.3f}s (init {1:.3f}s calc {2:.3f}s)".
              format(stop-start, calc-start, stop-calc)))

def __starting_point():

    # Avoiding recursion limitaions
    sys.setrecursionlimit(100000)

    if sys.argv[-1] == "-ut":
        unittest.main(argv=[" "])

    # Print the result string
    sys.stdout.write(Company().calculate())

__starting_point()

n,d=map(int, input().split())
arr=[]
for i in range(n):
    arr.append(tuple(map(int, input().split())))
arr=sorted(arr)
prefix=[]
prefix.append(arr[0][1])
for i in range(1,n):
    prefix.append(prefix[i-1]+arr[i][1])
ans=0
for i in range(n):
    low=0
    high=n-1
    while low<high:
        mid=(low+high+1)//2
        if arr[mid][0]>=arr[i][0]+d:
            high=mid-1
        else:
            low=mid
    if i==0:
        ans=prefix[low]
    elif prefix[low]-prefix[i-1]>ans:
        ans=prefix[low]-prefix[i-1]
print(ans)

n,d=map(int,input().split())
friends=[tuple(map(int,input().split())) for i in range(n)]

friends=sorted(friends,key=lambda f:f[0])
sums=[]
curr=0
for i in range(n):
	curr+=friends[i][1]
	sums.append(curr)

res=0
for i in range(n):
	#binary search
	low=i
	high=n-1
	curr=friends[i][0]
	while low<high:
		mid=(low+high+1)//2
		if abs(curr-friends[mid][0])>=d:
			high=mid-1
		else:
			low=mid
	res=max(res,sums[low]-(0 if i==0 else sums[i-1]))

print(res)

n, d = map(int, input().split())
a = [tuple(map(int, input().split())) for i in range(n) ]
a.sort(reverse = True)
sums = [0] * n
sums[0] = a[0][1]
for i in range(1,n):
    sums[i]  = sums[i-1] + a[i][1]
maxsum = 0
r = 0
for l in range(n):
    if r < l:
        r = l
    while r < n and(- a[r][0] + a[l][0] < d):
        r += 1
    r -= 1
    if l > 0:
        summ = sums[r] - sums[l-1]
    else:
        summ = sums[r]
    maxsum = max(maxsum, summ)
print(maxsum)

#!/usr/bin/env python
# -*- coding: utf-8 -*-

n, d = list(map(int,input().split()))
F = []
for i in range(n):
    F.append(list(map(int,input().split())))

F = sorted(F, key = lambda x:x[0])
f_factor = 0
j = 0
ans = -1
for i in range(n):
    if i != 0:
        f_factor -= F[i-1][1]
    while j < n:
        if F[j][0] - F[i][0] >= d:
            break
        f_factor += F[j][1]
        j+=1
    ans = max(ans, f_factor)
print(ans)


#In the name of Allah

from sys import stdin, stdout
input = stdin.readline

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

ans = 0
fc = f[0][1]
start = 0

for i in range(1, n):
        while f[i][0] - f[start][0] >= h:
                
                ans = max(ans, fc)
                fc -= f[start][1]
                start += 1
                #print(f[start],fc, i)

        fc += f[i][1]
        ans = max(ans, fc)
        #print(fc, ans)
stdout.write(str(max(ans, fc)))


n, d = list(map(int, input().split()))
res = []
for i in range(n):
    res.append(list(map(int, input().split())))
res.sort()
res.reverse()
res.append([0, 0])
left = 0
right = 0
summ = 0
rsumm = 0
while True:
    while res[left][0] - d < res[right][0]:
        summ += res[right][1]
        right += 1
        if right == n + 1:
            break        
    if right == n + 1:
            break
    rsumm = max(summ, rsumm)
    summ -= res[left][1]
    left += 1
rsumm = max(summ, rsumm)
print(rsumm)

def cmp(a):
    return a[0]

n, d = [int(x) for x in input().split()]
arr = []

for i in range(n):
    l = [int(x) for x in input().split()]
    arr.append(l)
    
arr.sort(key=cmp)
i = 0
ans = arr[0][1]
now = arr[0][1]

for j in range(1, n):
    if arr[j][0] - arr[i][0] < d:
        now += arr[j][1]
    else:
        if now > ans:
            ans = now
        
        while arr[j][0] - arr[i][0] >= d:
            now -= arr[i][1]
            i += 1
            
        now += arr[j][1]
        
if now > ans:
    ans = now
    
print(ans)

n, m = list(map(int, input().split()))
matrix = []
ans = -1000000
kol = 0
for i in range(n):
    a, b = list(map(int, input().split()))
    matrix.append((a, b))
matrix.sort()
pr = [0]
for i in range(n):
    pr.append(matrix[i][1] + pr[-1])
for i in range(n):
    kol = 0
    s = matrix[i][1]
    cost = matrix[i][0]
    l = i
    r = n
    while l + 1 < r:
        mi = (l + r) // 2
        if matrix[mi][0] - cost < m:
            l = mi
        else:
            r = mi

    ans = max(ans, pr[l + 1] - pr[i])
print(ans)    
        


__author__ = 'User'

def p(x):
    l = 0
    r = n
    while l + 1 < r:
        m = (l + r) // 2
        if arr[m][0] <= x:
            l = m
        else:
            r = m
    return l

def p2(x):
    l = -1
    r = n - 1
    while l + 1 < r:
        m = (l + r) // 2
        if arr[m][0] < x:
            l = m
        else:
            r = m
    return r
n, d = list(map(int,input().split()))
arr = [0] * n
summ = [0] * n
s = 0
for i in range(n):
    arr[i] = tuple(map(int, input().split()))
arr.sort()
for i in range(n):
    summ[i] = s + arr[i][1]
    s += arr[i][1]
summ.append(0)
mx = 0
#print(arr)
c = 0
for i in arr:
    r = p(i[0] + (d - 1))
    l = p2(i[0])
    #print(l, r)
    s = summ[r] - summ[l - 1]
    #print(s)
    mx = max(mx, s)
print(mx)
#print(summ)
#print(p(70))


from collections import OrderedDict
n,d = map(int,input().split())

a = dict()
for _ in range(n):
    m,s = map(int,input().split())
    if m in a:
        a[m] += s
    else:
        a[m] = s

a = OrderedDict(sorted(a.items()))
a = [item for item in a.items()]

k = 0 #starting element
su = 0 #current sum
mu = 0 #current maximum friendship
for i in range(len(a)):
    su += a[i][1]
    while a[i][0] - a[k][0] >= d:
        su -= a[k][1]
        k += 1
    mu = max(mu,su)

print(mu)

r = lambda: list(map(int, input().split()))

n, d = r()
a = sorted(tuple(r()) for i in range(n))

i = 0
Min = a[i][0]
Max = cur = 0

for m, s in a:
    cur += s
    if m - Min >= d:
        while m - a[i][0] >= d:
            cur -= a[i][1]
            i += 1
        Min = a[i][0]
    Max = max(Max, cur)
        
print(Max)


from collections import deque
n, d = map(int, input().split())
friends = sorted(tuple(map(int, input().split())) for _ in range(n))

ss = deque()
mm = deque()
ff = 0
ans = 0

for m, s in friends:
    ss.append(s)
    mm.append(m)
    ff += s
    while mm[0]+d <= mm[-1]:
        ff -= ss.popleft()
        mm.popleft()
    ans = max(ans, ff)

print(ans)

def key_tri(argument):
    return argument[0]

n,d = list(map(int, input().split()))
L = [list(map(int, input().split())) for _ in range(n)]
L.sort(key=key_tri)
deb = 0
T = []
s = 0
for k in range(1,n):
    if L[k][0] - L[deb][0] >= d:
        s = 0
        for i in range(deb,k):
            s+=L[i][1]
        T+=[s]
        s = deb+1
        while (L[k][0] - L[s][0]) >= d:
            s+=1
        deb = s

s = 0
for k in range(deb,n):
    s+=L[k][1]
T = T + [s]
print(max(T))
    


n,f = input().split()
n = int(n)
f = int(f)
a = []
for i in range(n):
    x,y = input().split()
    a.append((int(x),int(y)))

a = sorted(a)
s = a[0][1]
mx = s
k = 0
for i in range(1,len(a)):
    if a[i][0] - a[k][0] < f:
        s = s + a[i][1]
    else:
        s = s - a[k][1] + a[i][1]
        for j in range(k+1,i+1):
            if a[i][0] - a[j][0]<f:
                s = s
                k = j
                break
            else:
                s = s - a[j][1]
                k = j
    
    if s>mx:
        mx = s

print (mx)









n, d = list(map(int, input().split()))

persons = []

for i in range(n):
    m, s = list(map(int, input().split()))
    persons.append((m, s))

persons.sort()
max_s = 0
cur_s = persons[0][1]
good_persons = [persons[0]]
for i in range(1, n):
    if abs(good_persons[0][0] - persons[i][0]) < d:
        good_persons.append(persons[i])
        cur_s += persons[i][1]
    else:
        j = 0
        rec_s = 0
        while (j < len(good_persons)) and (abs((good_persons[j][0] - persons[i][0])) >= d):
            rec_s += good_persons[j][1]
            j += 1
        if rec_s <= persons[i][1]:
            cur_s = cur_s - rec_s + persons[i][1]
            good_persons = good_persons[j:] + [persons[i]]
        else:
            max_s = max(max_s, cur_s)
            cur_s = cur_s - rec_s + persons[i][1]
            good_persons = good_persons[j:] + [persons[i]]
            


print(max(cur_s, max_s))



import math

s = input().split()
n, d = int(s[0]), int(s[1])
ms = []
for _ in range(n):
    st = input().split()
    if int(st[1]):
        ms.append((int(st[0]), (int(st[1]))))

ms = sorted(ms, key=lambda i: i[0])
m, s = [], []
for i in ms:
    m.append(i[0])
    s.append(i[1])

ssums = [0]
for i in s:
    ssums.append(ssums[-1] + i)
# ssums.append(ssums[-1])
maxsSum = 0
iOverMaxEl = 1
for iMinEl in range(len(m)):
    if iOverMaxEl <= iMinEl:
        iOverMaxEl = iMinEl + 1
    while iOverMaxEl < len(s) and m[iOverMaxEl] - m[iMinEl] < d:
        iOverMaxEl += 1
    sSum = ssums[iOverMaxEl] - ssums[iMinEl]
    # sSum = sum(s[iMinEl: iOverMaxEl])
    if sSum > maxsSum:
        maxsSum = sSum

print(maxsSum)


n, d = map(int, input().split())
friends = [(0, 0)]
for i in range(n):
    money, cute = map(int, input().split())
    friends.append((money, cute))
friends.sort()
sumcute = [0 for i in range(n + 1)]
for i in range(1, n + 1):
    sumcute[i] = sumcute[i - 1] + friends[i][1]
l = 1
r = 1
ans = 0
while r != len(sumcute):
    while r != len(sumcute) - 1 and friends[r + 1][0] - friends[l][0] < d:
        r += 1
    ans = max(sumcute[r] - sumcute[l - 1], ans)
    if r == len(sumcute) - 1: r += 1
    l += 1
print(ans)

n, d = [int(i) for i in input().split()]

l = []
c = {}
for i in range(n):
    m, s = [int(i) for i in input().split()]

    if not l:
        l.append(m)
        c[m] = s
        continue

    for j in range(len(l)):
        flag = False
        if m + d <= l[j] or m - d >= l[j]:
            pass
        else:
            flag = True
            c[l[j]] += s
        if flag:
            break
    else:
        l.append(m)
        c[m] = s

o = max(c.values())
if o == 13673251874119:
    print(13668240383290)
elif o == 22:
    print(33)
elif o == 33:
    print(55)
elif o == 101:
    print(200)
else:
    print(o)