import sys
input = sys.stdin.readline

N,D=list(map(int,input().split()))
P=[list(map(int,input().split())) for i in range(N)]

OK=-1<<60
NG=1

while OK<NG-1:
    mid=(OK+NG)//2

    DP=[0]*N
    LEFT=[0]*N
    RIGHT=[0]*N

    for day in range(D):
        NDP=[-1<<60]*N

        for i in range(N):
            if i+1<N and LEFT[i+1]-P[i][0]>=mid:
                NDP[i]=max(NDP[i],LEFT[i+1]-P[i][0]+P[i][1])
            if i-1>=0 and RIGHT[i-1]-P[i][0]>=mid:
                NDP[i]=max(NDP[i],RIGHT[i-1]-P[i][0]+P[i][1])

        DP=NDP

        LEFT=[-1<<60]*N
        RIGHT=[-1<<60]*N

        LEFT[-1]=DP[-1]
        for i in range(N-2,-1,-1):
            LEFT[i]=max(LEFT[i+1],DP[i])
        RIGHT[0]=DP[0]
        for i in range(1,N):
            RIGHT[i]=max(RIGHT[i-1],DP[i])

    if max(DP)<=-1<<60:
        NG=mid
    else:
        OK=mid

print(OK)