Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

I = list(map(int, input().split()))
N = I[0]
K = I[1]
H = list(map(int, input().split()))

dp = [float('inf') for _ in range(N+1)]

dp[N] = 0
dp[N-1] = abs(H[N-1]-H[N-2])
for i in range(N-2,0,-1):
	for k in range(1,K+1):
		if i+k<=N:
			dp[i] = min(abs(H[i+k-1]-H[i-1])+dp[i+k], dp[i])

print(dp[1])

### FIXED CODE ###

I = list(map(int, input().split()))
N = I[0]
K = I[1]
H = list(map(int, input().split()))

dp = [float('inf') for _ in range(N+1)]

dp[N] = 0
for i in range(N-1,N-K-1,-1):
	if i>0:
		dp[i] = abs(H[i-1]-H[N-1])

for i in range(N-K-1,0,-1):
	for k in range(1,K+1):
		if i+k<=N:
			dp[i] = min(abs(H[i+k-1]-H[i-1])+dp[i+k], dp[i])

print(dp[1])
### BUGGY CODE ###

# ABC152F

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")





from collections import defaultdict
from queue import deque
import itertools
import functools
def find(start,goal):
    q = deque([start])
    seen = [None] * n
    seen[start] = -1
    while q:
        u = q.pop()
        d = seen[u]
        if u==goal:
            break
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    u = goal
    es = []
    while True:
        t = (min(u, seen[u]), max(u, seen[u]))
        es.append(t)
        if seen[u]==start:
            break
        u = seen[u]
    return set(es)

n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
ans = 0
m = int(input())
paths = [None] * m
for i in range(m):
    u, v = map(int, input().split())
    paths[i] = find(u-1,v-1)

ans = 0
for ind in itertools.product(*[(True, False) for _ in range(m)]):
    num = sum(ind)+1
    if num==1:
        continue
    c = 2**(n - 1 - len(functools.reduce(lambda x,y: x|y, (paths[i] for i in range(m) if ind[i]), set())))
    ans += (-1)**num * c
print(2**(n-1) - ans)

### FIXED CODE ###

# ABC152F

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")





from collections import defaultdict
from queue import deque
import itertools
import functools
def find(start,goal):
    q = deque([start])
    seen = [None] * n
    seen[start] = -1
    while q:
        u = q.pop()
        d = seen[u]
        if u==goal:
            break
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    u = goal
    es = []
    while True:
        t = (min(u, seen[u]), max(u, seen[u]))
        es.append(t)
        if seen[u]==start:
            break
        u = seen[u]
    return set(es)

n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
ans = 0
m = int(input())
paths = [None] * m
for i in range(m):
    u, v = map(int, input().split())
    paths[i] = find(u-1,v-1)

ans = 0

def dfs(ind, s, ans):
    if len(ind)==m:
        if True in ind:
            ans += 2**(n-1-len(s)) * (-1)**(sum(ind)+1)
        return ans
    ans = dfs(ind + [True], s | paths[len(ind)], ans)
    ans = dfs(ind + [False], s, ans)
    return ans
        
# for ind in itertools.product(*[(False, True) for _ in range(m)]):
#     num = sum(ind)+1
#     if num==1:
#         continue
#     c = 2**(n - 1 - len(functools.reduce(lambda x,y: x|y, (paths[i] for i in range(m) if ind[i]), set())))
#     ans += (-1)**num * c
ans = dfs([], set(), 0)
print(2**(n-1) - ans)
### BUGGY CODE ###

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, q = read_line(int, int)
s, = read_line(str)

p = []
i = 0
while i < len(s) - 1:
    if s[i:i+2] == 'AC':
        p.append(i)
        i += 2
    else:
        i += 1

for i in range(q):
    l, r = read_line(int, int)
    l, r = l - 1, r - 1

    c = 0
    for pp in p:
        if l <= pp and pp + 1 <= r:
            c += 1
    print(c)


### FIXED CODE ###

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, q = read_line(int, int)
s, = read_line(str)

m = [0 for _ in range(len(s) + 1)]

c = 0
for i in range(len(s)):
    if s[i:i+2] == 'AC':
        c += 1
    m[i + 1] = c

for i in range(q):
    l, r = read_line(int, int)

    if c == 0:
        print(0)
        continue
    print(m[r - 1] - m[l - 1])
### BUGGY CODE ###

import queue
import sys
sys.setrecursionlimit(5*10**5)

N, Q = map(int, input().split())
ab=[]
for _ in range(N-1):
    ab.append(tuple(map(int, input().split())))
px=[]
for _ in range(Q):
    px.append(tuple(map(int, input().split())))

cnt=[0]*(N+1)
for el in px:
    cnt[el[0]]+=el[1]
#print(cnt)


lst=[[] for _ in range(N+1)]
for el in ab:
    lst[el[0]].append(el[1])
    lst[el[1]].append(el[0])
#print(lst)

seen = [False] * (N + 1)
def dfs(n):
    seen[n] = True
    for child in lst[n]:
        if seen[child] == False:
            cnt[child]+=cnt[n]
            dfs(child)

dfs(1)
#print(cnt)
print(' '.join(list(map(str, cnt[1:]))))

### FIXED CODE ###

import sys
sys.setrecursionlimit(5*10**5)
input = sys.stdin.readline

N, Q = map(int, input().split())
ab=[]
for _ in range(N-1):
    ab.append(tuple(map(int, input().split())))
px=[]
for _ in range(Q):
    px.append(tuple(map(int, input().split())))

cnt=[0]*(N+1)
for el in px:
    cnt[el[0]] += el[1]
#print(cnt)


lst=[[] for _ in range(N+1)]
for el in ab:
    lst[el[0]].append(el[1])
    lst[el[1]].append(el[0])
#print(lst)

seen = [False] * (N + 1)
def dfs(n):
    seen[n] = True
    for child in lst[n]:
        if seen[child] == False:
            cnt[child]+=cnt[n]
            dfs(child)

dfs(1)
#print(cnt)
print(' '.join(list(map(str, cnt[1:]))))
### BUGGY CODE ###

N = int(input())

count = 0
for i in range(1,N+1):
    li = i//10**(len(str(i))-1) 
    ri = i%10
    for j in range(i,N+1):
        lj = j//10**(len(str(j))-1)
        rj = j%10
        if li == rj and lj == ri:
            if i == j:
                count += 1
            else:
                count += 2

print(count)

### FIXED CODE ###

N = int(input())
c = [[0]*9 for _ in range(9)]
count = 0
for i in range(1,N+1):
    li = i//10**(len(str(i))-1) 
    ri = i%10
    if ri == 0:
        continue
    c[li-1][ri-1] += 1

for i in range(9):
    for j in range(9):
        count += c[i][j]*c[j][i]

print(count)
### BUGGY CODE ###

M = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

zero = [0] * 60
one = [1] * 60
pow2 = [2 ** i % M for i in range(60)]


def bitcnt(a):
    j = 0
    bits = [0] * 60
    while a:
        bits[j] = a & 1
        a >>= 1
        j += 1
    return bits


ans = 0
a1 = bitcnt(A[0])
a0 = [(x + 1) % 2 for x in a1]
for i in range(1, N):
    bits1 = bitcnt(A[i])
    bits0 = [(x + 1) % 2 for x in bits1]
    ans += sum(pow2[i] * (a0[i] * bits1[i] % M) % M for i in range(60))
    ans %= M
    ans += sum(pow2[i] * (a1[i] * bits0[i] % M) % M for i in range(60))
    ans %= M
    a1 = [(a1[i] + bits1[i]) % M for i in range(60)]
    a0 = [(a0[i] + bits0[i]) % M for i in range(60)]

print(ans)


### FIXED CODE ###

M = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

zero = [0] * 60
one = [1] * 60
pow2 = [2 ** i % M for i in range(60)]


def bitcnt(a):
    j = 0
    bits = [0] * 60
    while a:
        bits[j] = a & 1
        a >>= 1
        j += 1
    return bits


ans = 0
a1 = bitcnt(A[0])
a0 = [(x + 1) % 2 for x in a1]
for i in range(1, N):
    a = A[i]
    for j in range(60):
        b1 = a & 1
        a >>= 1
        if b1:
            ans += pow2[j] * a0[j] % M
            a1[j] += 1
        else:
            ans += pow2[j] * a1[j] % M
            a0[j] += 1
        ans %= M

print(ans)
### BUGGY CODE ###

n, k, q = map(int, input().split())
#print(n,k,q)
l = [0] * n
#print(l)
katen = []
for i in range(q):
    katen.append(int(input()))
#print(katen)
for j in katen:
#    x = 
    l.insert(j-1, l.pop(j-1)+1)
#print(l)

for y in l:
    if y > q-k:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n, k, q = map(int, input().split())
#print(n,k,q)
l = [0] * n
#print(l)
katen = []
my_append = katen.append
for i in range(q):
    my_append(int(input()))
#print(katen)

    
for j in katen:
    l[j-1] += 1 

    
#print(l)

for y in range(n):
    if l[y] > q-k:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = ((sum(p[:k])+k))/2
for i in range(1, n-k+1):
    ans_2 = (sum(p[(i):(k+i)])+k)/2
    ans = max([ans, ans_2])
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
tmp = sum(p[:k])
ans = [tmp]
if n == k:
    ans_mae = ans[0]
    print((ans_mae+k)/2)
else:
    for i in range(1,n-k+1):
        tmp = tmp - p[i-1] + p[i+k-1]
        ans.append(tmp)
    print((max(ans)+k)/2)
### BUGGY CODE ###

N,Y = map(int,input().split())
cnt10 = 0
cnt5 = 0
cnt1 = 0
def wrong():
	print('-1 -1 -1')
	exit()
all1000 = int(Y / 1000)
if all1000 % 1 != 0:
	wrong()
for x in range(all1000 + 1):
	for y in range(all1000 - x + 1):
		if N - x - y < 0:
			continue
		if x * 10 + y * 5 + (N - x - y) == all1000:
			print('{} {} {}'.format(x,y,N - x - y))
			exit()
print('-1 -1 -1')


### FIXED CODE ###

N,Y = map(int,input().split())
cnt10 = 0
cnt5 = 0
cnt1 = 0
def wrong():
	print('-1 -1 -1')
	exit()
all1000 = int(Y / 1000)
if all1000 % 1 != 0:
	wrong()
for x in range(all1000 + 1):
	for y in range(all1000 - x + 1):
		if N - x - y < 0:
			break
		if x * 10 + y * 5 + (N - x - y) == all1000:
			print('{} {} {}'.format(x,y,N - x - y))
			exit()
print('-1 -1 -1')
### BUGGY CODE ###

s = input()
K = int(input())
length = len(s)

substringList = []
for i in range(1,length+1) :
    for j in range(length-i+1) :
        substringList.append(s[j:j+i])


substringList = sorted(list(set(substringList)))
print(substringList[K-1])


### FIXED CODE ###

s = input()
K = int(input())
length = len(s)

substringList = []
for i in range(1,K+1) :
    for j in range(length-i+1) :
        substringList.append(s[j:j+i])


substringList = sorted(list(set(substringList)))
print(substringList[K-1])
### BUGGY CODE ###

n = int(input())
c = []
s = []
f = []
for i in range(n - 1):
    C, S, F = map(int, input().split())
    c.append(C)
    s.append(S)
    f.append(F)
for i in range(n - 1):
    ans = s[i] + c[i]
    for j in range(i + 1, n - 1):
        noru = s[j]
        while noru < ans:
            noru += f[j]
        ans += noru - ans + c[j]
    print(ans)
print(0)

### FIXED CODE ###

n = int(input())
c = []
s = []
f = []
for i in range(n - 1):
    C, S, F = map(int, input().split())
    c.append(C)
    s.append(S)
    f.append(F)
for i in range(n - 1):
    ans = 0
    for j in range(i, n - 1):
        if ans < s[j]:
            ans = s[j]
        elif ans % f[j] == 0:
            pass
        else:
            ans += f[j] - ans % f[j]
        ans += c[j]
    print(ans)
print(0)
### BUGGY CODE ###

def check(x, y, K, S):
  for z in range(K+1):
    if x + y + z == S:
      return True
  return False

K, S = list(map(int, input('').split()))
count = 0
for x in range(K+1):
  for y in range(K+1):
    if check(x, y, K, S):
      count += 1
print(count)

### FIXED CODE ###

K, S = list(map(int, input('').split()))
count = 0
for x in range(K+1):
  for y in range(K+1):
    if x + y <= S and x + y + K >= S:
      count += 1
print(count)
### BUGGY CODE ###

import itertools
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				break
		B = B[:bi + 1]
		for i in range(1,len(B) + 1):
			C = list(itertools.combinations(B,i))
			for c in C:
				if sum(c) in fusoku:
					need.append(a)
					z = 1
					break
			if z == 1:
				break
		if z == 0:
			iranaiko.append(a)
print(N - len(need))


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				bi = bi - 1
				break
		B = B[:bi + 1]
		B.reverse()
		C = [0]
		for b in B:
			D = []
			for c in C:
				if b + c < K:
					if b + c in fusoku:
						z = 1
						need.append(a)
						break
					D.append(b + c)
				
			D.append(0)
			C = D[:]
			if z == 1:
				break
			
		if z == 0:
			iranaiko.append(a)

print(N - len(need))
### BUGGY CODE ###

from collections import deque


H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for i in range(H)]

dist = [[10**9+7] * W for _ in range(H)]
Ch = Ch-1
Cw = Cw-1
Dh = Dh-1
Dw = Dw-1

queue = deque()
queue.append((Ch,Cw))
queue2 = deque()
dist[Ch][Cw] = 0

walk = [[0,1],[1,0],[0,-1],[-1,0]]
    
while len(queue) > 0:
    while len(queue) > 0:
        h, w = queue.popleft()
        d = dist[h][w]
        flag = 0
        for vh,vw in walk:
            nh = h + vh
            nw = w + vw
            if 0 <= nh and nh < H and 0 <= nw and nw < W:
                if S[nh][nw] == '.':
                    if dist[nh][nw] > d:
                        dist[nh][nw] = d
                        queue.append([nh,nw])
                else:
                        flag += 1
        if flag:
            queue2.append([h,w])
            
    while len(queue2) > 0:
        h, w = queue2.popleft()
        for vh in range(-2,3):
            for vw in range(-2,3):
                nh = h + vh
                nw = w + vw
                if 0 <= nh and nh < H and 0 <= nw and nw < W:
                    if S[nh][nw] == '.' and dist[nh][nw] == 10**9+7:
                        dist[nh][nw] = dist[h][w] + 1
                        queue.append([nh,nw])
                
if dist[Dh][Dw] != 10**9+7:
    print(dist[Dh][Dw])
else:
    print(-1)


### FIXED CODE ###

from collections import deque


H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for i in range(H)]

dist = [[10**9+7] * W for _ in range(H)]
Ch = Ch-1
Cw = Cw-1
Dh = Dh-1
Dw = Dw-1

queue = deque()
queue.append((Ch,Cw))
queue2 = deque()
dist[Ch][Cw] = 0

walk = [[0,1],[1,0],[0,-1],[-1,0]]
    
while len(queue) > 0:
    while len(queue) > 0:
        h, w = queue.popleft()
        d = dist[h][w]
        flag = 0
        for vh,vw in walk:
            nh = h + vh
            nw = w + vw
            if 0 <= nh and nh < H and 0 <= nw and nw < W:
                if S[nh][nw] == '.':
                    if dist[nh][nw] > d:
                        dist[nh][nw] = d
                        queue.append([nh,nw])
                else:
                        flag += 1
        if flag:
            queue2.append([h,w])
            
    while len(queue2) > 0:
        h, w = queue2.popleft()
        for vh in range(-2,3):
            for vw in range(-2,3):
                nh = h + vh
                nw = w + vw
                if 0 <= nh and nh < H and 0 <= nw and nw < W:
                    if S[nh][nw] == '.' and dist[nh][nw] == 10**9+7:
                        dist[nh][nw] = dist[h][w] + 1
                        queue.append([nh,nw])
                
if dist[Dh][Dw] != 10**9+7:
    print(dist[Dh][Dw])
else:
    print(-1)
### BUGGY CODE ###


N, K, Q = list(map(int, input().split()))

ans = [K] * N

for i in range(Q):
    n = int(input())
    ans = list(map(lambda x:x - 1, ans))
    ans[n - 1] += 1

for i in range(N):
    if ans[i] > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###


N, K, Q = list(map(int, input().split()))

ans = [K] * N

for i in range(Q):
    n = int(input())
    ans[n - 1] += 1

for i in range(N):
    if ans[i] - Q > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N, M = map(int, input().split())
from collections import deque
AB = deque(sorted([list(map(int, input().split())) for i in range(N)]))

from heapq import *
q = []
heapify(q)
ans = 0
remain_days = 1
while remain_days <= M:
    for a, b in list(AB):
        if a <= remain_days:
            heappush(q, -1 * AB.popleft()[1])
    if q:
        v = heappop(q)
        ans += -1 * v
    remain_days += 1
print(ans)

### FIXED CODE ###

from heapq import *
n, m = map(int, input().split())
jobs = [tuple(map(int, input().split())) for _ in range(n)]
jobs.sort(reverse=True)
ans = 0
q = []
# 残り何日でのごとの仕事の候補をqに追加していく
for i in range(1, m+1):
    while jobs and jobs[-1][0] <= i:
        # -1かけてqに追加
        heappush(q, -jobs.pop(-1)[1])
    if q:
        #　残り何日でごとに、-1かかってるので一番高いお金をもらえる仕事がpopされる
        ans -= heappop(q)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
h,w=map(int,input().split())
a_list=[]
for i in range(h):
    b=list(input())
    a_list.append(b)
dp=[]
for i in range(h):
    dps=[]
    for j in range(w):
        dps.append(10**9)
    dp.append(dps)
def f(x,y):
    if dp[x][y]<10**9:
        return dp[x][y]
    else:
        if a_list[x][y]=='#':
            dp[x][y]=0
            return 0
        else:
            dp[x][y]=10**8
            if x>0:
                k0=f(x-1,y)+1
            else:
                k0=10**9
            if x<h-1:
                k1=f(x+1,y)+1
            else:
                k1=10**9
            if y>0:
                k2=f(x,y-1)+1
            else:
                k2=10**9
            if y<w-1:
                k3=f(x,y+1)+1
            else:
                k3=10**9
            m=min(k0,k1,k2,k3)
            dp[x][y]=m
            return m
answer=0
for i in range(h):
    for j in range(w):
        answer=max(answer,f(i,j))
print(answer)

        


### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
INF=10**9
check=[]
for i in range(h):
    sub_list=[]
    for j in range(w):
        sub_list.append(INF)
    check.append(sub_list)
black=deque([])
for i in range(h):
    sub_list=list(input())
    for j in range(w):
        if sub_list[j]=='#':
            black.append((i,j))
            check[i][j]=0
Max=0
while len(black)>0:
    now=black.popleft()
    U=(now[0]-1,now[1])
    D=(now[0]+1,now[1])
    L=(now[0],now[1]-1)
    R=(now[0],now[1]+1)
    for i in U,D,L,R:
        if 0<=i[0]<=h-1 and 0<=i[1]<=w-1 and check[i[0]][i[1]]==INF:
            check[i[0]][i[1]]=check[now[0]][now[1]]+1
            Max=max(Max,check[i[0]][i[1]])
            black.append(i)
print(Max)
### BUGGY CODE ###

n, m = map(int, input().split())
gates = []
count = 0
for gate in range(m):
    gates.append(list(map(int, input().split())))
for card in range(n):
    card+=1
    token = True
    for gate in range(m):
        if (card < gates[gate][0] or gates[gate][1] < card):
            token = False
            break
    if token:
        count +=1
print(count)

### FIXED CODE ###

n, m = map(int, input().split())
gates = []
for i in range(m):
    gates.append(list(map(int, input().split())))
candidate = [1, n]
for gate in gates:
    if candidate[0] < gate[0]:
        candidate[0] = gate[0]
    if gate[1] < candidate[1]:
        candidate[1] = gate[1]
if (candidate[1] >= candidate[0]):
    print(candidate[1] - candidate[0] + 1)
else:
    print(0)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
ans_list = []

for i in range(N):
    A = int(input())
    if A in ans_list:
        ans_list.remove(A)
    else:
        ans_list.append(A)

print(len(ans_list))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())

# 集合　listよりも 検索などが高速
# 重複なしの順序も無し
ans_set = set()

for i in range(N):
    A = int(input())
    if A in ans_set:
        ans_set.remove(A)
    else:
        ans_set.add(A)

print(len(ans_set))
### BUGGY CODE ###

s = input()
k = int(input())
l = []
for i in s:
    l.append(str(int(i)**(5*10**15)))
print("".join(l)[k-1])



### FIXED CODE ###

s = input()
k = int(input())
cnt = 0
x = 0
for i in s:
    if i == "1":
        cnt += 1
    else:
        x = int(i)
        break
if k<=cnt:
    print(1)
else:
    print(x)
### BUGGY CODE ###

N, C = map(int, input().split())
X = []
V = []
for _ in range(N):
  x, v = map(int, input().split())
  X.append(x)
  V.append(v)

A = [0] * (N + 1)
A_max = [0] * (N + 1)
B = [0] * (N + 1)
B_max = [0] * (N + 1)
for i in range(N):
  A[i + 1] = sum(V[:i + 1]) - X[i]
  A_max[i + 1] = max(A)
  B[i + 1] = sum(V[- i - 1:]) - (C - X[- i - 1])
  B_max[i + 1] = max(B)

X = [0] + X
V = [0] + V

m = max(0, A_max[-1], B_max[-1])
for i in range(1, N + 1):
  m = max(m, A[i] + B_max[N - i] - X[i], B[i] + A_max[N - i] - (C - X[N - i + 1]))

print(m)

### FIXED CODE ###

N, C = map(int, input().split())
X = []
V = []
for _ in range(N):
  x, v = map(int, input().split())
  X.append(x)
  V.append(v)

A = [0] * (N + 1)
A_max = [0] * (N + 1)
B = [0] * (N + 1)
B_max = [0] * (N + 1)
a_sum = 0
b_sum = 0
for i in range(N):
  a_sum += V[i]
  A[i + 1] = a_sum - X[i]
  A_max[i + 1] = max(A_max[i], A[i + 1])
  b_sum += V[- i - 1]
  B[i + 1] = b_sum - (C - X[- i - 1])
  B_max[i + 1] = max(B_max[i], B[i + 1])

X = [0] + X
V = [0] + V

m = max(0, A_max[-1], B_max[-1])
for i in range(1, N + 1):
  m = max(m, A[i] + B_max[N - i] - X[i], B[i] + A_max[N - i] - (C - X[N - i + 1]))

print(m)
### BUGGY CODE ###

n = int(input())
num = input().split()
 
def check():
  for s in num:
    if(num.count(s) >= 2):
      print("NO")
      return
  print("YES")

check()

### FIXED CODE ###

n = int(input())
num = input().split()

if len(set(num)) == n:
  print("YES")
else:
  print("NO")
### BUGGY CODE ###


import itertools


N = int(input())
li = list(map(int, input().split()))
MOD_NUMBER = 10**9+7
moded_li = []
for i in li:
    ans = i % MOD_NUMBER
    if ans != 0:
        moded_li.append(ans)
ans = 0
for idx in range(len(moded_li)-1):
    ans += moded_li[idx] * sum(moded_li[idx+1:])

print(ans % MOD_NUMBER)


### FIXED CODE ###


N = int(input())
li = list(map(int, input().split()))
MOD_NUMBER = 10**9+7
nizyo_list = [i**2 for i in li]
ans = (sum(li)**2-sum(nizyo_list))//2
print(ans % MOD_NUMBER)
### BUGGY CODE ###

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

dict_B={}
dict_A={}
B=list(set(A))
sum=0
C=0

for b in B:
    a=A.count(b)
    dict_A[b]=(a-1)*(a-2)//2
    dict_B[b]=a*(a-1)//2
    sum+=a*(a-1)//2

for a in A:
    print(sum-dict_B[a]+dict_A[a])

        

### FIXED CODE ###

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


dict_A={}
B=list(set(A))
sum=0


for a in A:
    if a not in dict_A.keys():
        dict_A[a]=1
    else:
        dict_A[a]+=1
for b in B:
    sum+=dict_A[b]*(dict_A[b]-1)//2

for a in A:
    print(sum-dict_A[a]+1)
### BUGGY CODE ###

def main():
    from fractions import gcd
    import sys
    n=int(input())
    a = tuple(map(int, input().split()))
    ans = a[0]

    #mmm=10**9+7
    for i in a[1:]:
        ans = ans *i // gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

    print(result%(10**9+7))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from fractions import gcd
    import sys
    n=int(input())
    a = tuple(map(int, input().split()))
    ans = 1

    mmm=10**9+7
    for i in a:
        ans = ans *i // gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

    print(result%mmm)

if __name__ == '__main__':
    main()