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

a = input()
b = input()
c = input()

# 文字のマッチング(?はワイルドカード)
def match(a, b):
    return a=="?" or b=="?" or a==b

ab = [True] * 100000 # Aに対して(i-50000)個左にスライドした位置にBを置けるか？
ac = [True] * 100000 # Aに対して(i-50000)個左にスライドした位置にCを置けるか？
bc = [True] * 100000 # Bに対して(i-50000)個左にスライドした位置にCを置けるか？

def check(a, b, ab):
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i], b[j]):
                ab[i-j+50000] = False

check(a, b, ab)
check(a, c, ac)
check(b, c, bc)

len_max = 2000
len_a = len(a)
len_b = len(b)
len_c = len(c)

ans = len_a + len_b + len_c

# i = BをAに対していくつスライドして置くか
for i in range(-2 * len_max, 2 * len_max + 1):
    # j = CをAに対していくつスライドして置くか
    for j in range(-2 * len_max, 2 * len_max + 1):
        if ab[i+50000] and ac[j+50000] and bc[j-i+50000]:
            left = min(0, i, j)
            right = max(len_a, len_b+i, len_c+j)
            size = right - left
            if size < ans:
                ans = size

print(ans)

### FIXED CODE ###

import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def match(a, b):
    return a=="?" or b=="?" or a==b

a = input()
b = input()
c = input()



# aに対して(i-50000)個左にスライドした位置にbを置けるか？
ab = [True] * 100000
ac = [True] * 100000
bc = [True] * 100000

def check(a,b, ab):
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i], b[j]):
                ab[i-j+50000] = False

log("check end.")

check(a, b, ab)
check(a, c, ac)
check(b, c, bc)

len_max = 2000
len_a = len(a)
len_b = len(b)
len_c = len(c)

ans = 9999999999999999999999

for i in range(-2 * len_max, 2 * len_max + 1):
    for j in range(-2 * len_max, 2 * len_max + 1):
        if ab[i+50000] and ac[j+50000] and bc[j-i+50000]:
            left = min(0, i, j)
            right = max(len_a, len_b+i, len_c+j)
            ans = min(ans, right - left)

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

import sys
import fractions
from functools import reduce

def input():
	return sys.stdin.readline()

def gcd(num):
	return reduce(fractions.gcd, num)

N = int(input())
A = [int(_) for _ in input().split()]

ans = 0
for i in range(N):
	if i == 0:
		A_ = A[1:]
	elif i == N-1:
		A_ = A[:-1]
	else:
		A_ = A[:i]+A[i+1:]
	ans = max(ans, gcd(A_))

print(ans)

### FIXED CODE ###

import sys
from fractions import gcd

def input():
	return sys.stdin.readline()

N = int(input())
A = [int(_) for _ in input().split()]
p1 = [0] * N
p2 = [0] * N

p1[0] = A[0]
p2[-1] = A[-1]

for i in range(1, N):
	p1[i] = gcd(p1[i-1], A[i])
	p2[-(i+1)] = gcd(p2[-i], A[-(i+1)])

m = max(p1[-2], p2[1])

if N > 2:
	for i in range(1, N-1):
		m = max(m, gcd(p1[i-1], p2[i+1]))

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

import math
K = int(input())
ans = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            ans += math.gcd(i+1, math.gcd(j+1, k+1))
print(ans)


### FIXED CODE ###

import math
K = int(input())
ans = 0
for i in range(1, K+1):
    for j in range(i, K+1):
        for k in range(j, K+1):
            if (i == j) and (j == k):
                ans += math.gcd(i, math.gcd(j, k))
            elif (i == j) or (j == k):
                ans += 3 * math.gcd(i, math.gcd(j, k))
            else:
                ans += 6 * math.gcd(i, math.gcd(j, k))
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
H, W = map(int, input().split())
S = [input() for _ in range(H)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y, count, i):
	nx = x + dx[i]
	ny = y + dy[i]
	if nx >= 0 and nx < H and ny >= 0 and ny < W and S[nx][ny] == '.':
		return dfs(nx, ny, count + 1, i)
	else:
		return count
		
ans = 0

for sx in range(H):
	for sy in range(W):
		if S[sx][sy] == '.':
			tmp = 1
			for i in range(4):
				tmp += dfs(sx, sy, 0, i)
				
			if tmp > ans:
				ans = tmp
				
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
H, W = map(int, input().split())
S = [input() for _ in range(H)]
R = [[0] * W for _ in range(H)]
L = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]

for i in range(H):
	for j in range(W):
		if S[i][j] == '.':
			if j > 0:
				L[i][j] = L[i][j - 1] + 1
			elif j == 0:
				L[i][j] = 1
				
			if i > 0:
				U[i][j] = U[i - 1][j] + 1
			elif i == 0:
				U[i][j] = 1
		
		if S[i][W - j - 1] == '.':
			if j > 0:
				R[i][W - j - 1] = R[i][W - j] + 1
			elif j == 0:
				R[i][W - j - 1] = 1
		
		if S[H - i - 1][j] == '.':
			if i > 0:
				D[H - i - 1][j] = D[H - i][j] + 1
			elif i == 0:
				D[H - i - 1][j] = 1
			
ans = 0
for i in range(H):
	for j in range(W):
		tmp = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
		if tmp > ans:
			ans = tmp
			
print(ans)
### BUGGY CODE ###

s=input()
s=list(s)
n=len(s)
for i in range(0,n):
    if i!=(n-1):
        if s[i]=='?' and s[i+1]=='P':
            s[i]='D'
        elif (s[i]=='?'):
            s[i]='P'
    else:
        if s[i]=='?':
            s[i]='D'
ans=""
for i in s:
    ans+=i
print(ans)

### FIXED CODE ###

s=input()
n=len(s)
for i in range(0,n):
    if(s[i]=='?'):
        print('D',end="")
    else:
        print(s[i],end="")
### BUGGY CODE ###

s = input()
lst = []
for i in range(len(s)):
    lst.append(int(s[-1-i:]) % 2019)
lst.sort()

total = 0
cnt = 1
before = 0
for num in lst:
    if before == num:
        cnt += 1
    else:
        total += cnt * (cnt - 1) // 2
        cnt = 1
    before = num
total += cnt * (cnt - 1) // 2
print(total)

### FIXED CODE ###

s = input()[::-1]

lst = []
num = 1
pow10 = [1]
for _ in range(len(s) - 1):
    num = num * 10 % 2019
    pow10.append(num)

num = 0
for s_num, p10 in zip(s, pow10):
    num = (num + (int(s_num) * p10)) % 2019
    lst.append(num)
lst.sort()

total = 0
cnt = 1
before = 0
for num in lst:
    if before == num:
        cnt += 1
    else:
        total += cnt * (cnt - 1) // 2
        cnt = 1
    before = num
total += cnt * (cnt - 1) // 2
print(total)
### BUGGY CODE ###

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

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if j - i == A[i] + A[j]:
            ans += 1

print(ans)


### FIXED CODE ###

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

L = {}
R = {}
for i, a in enumerate(A):
    x = i + 1 + a
    L[x] = L[x] + 1 if x in L else 1

    x = i + 1 - a
    R[x] = R[x] + 1 if x in R else 1

# print(L, R)

ans = 0
for x in L.keys():
    ans += L[x] * (R[x] if x in R else 0)

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

import sys, numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson  
from collections import defaultdict
from itertools import product, permutations, combinations

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

def solve():
    N, u, v = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N-1)]

    adjm = [[float('inf')] * N for _ in range(N)]
    for ab in AB:
        a, b = ab[0]-1, ab[1]-1
        adjm[a][b] = 1
        adjm[b][a] = 1
        
    dv = dijkstra(adjm, indices=v-1)
    du = dijkstra(adjm, indices=u-1)
    dOK = [i for i, j in zip(dv, du) if i>j]

    print(int(max(dOK)-1))

solve()


### FIXED CODE ###

import sys, heapq
from collections import defaultdict
from itertools import product, permutations, combinations

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

N, u, v = map(int, input().split())



def dijkstra_heap(s,edge):
#始点sから各頂点への最短距離
    d = [10**20] * N
    used = [True] * N #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

AB = [list(map(int, input().split())) for _ in range(N-1)]

adjl = [[] for _ in range(N)]
for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    adjl[a].append([1, b])
    adjl[b].append([1, a])

du = dijkstra_heap(u-1, adjl)
dv = dijkstra_heap(v-1, adjl)
dOK = [j for i, j in zip(du, dv) if i < j]

print(int(max(dOK)-1))
### BUGGY CODE ###

s,t=map(lambda x:sorted(x.count(i)for i in x),open(0))
print('YNeos'[s!=t::2])

### FIXED CODE ###

s,t=[0]*26,[0]*26
for a,b in zip(input(),input()):
  s[ord(a)-ord('a')]+=1
  t[ord(b)-ord('a')]+=1
u,v=[],[]
for a,b in zip(s,t):
  if a!=b:
    u.append(a)
    v.append(b)
print('YNeos'[sorted(u)!=sorted(v)::2])
### BUGGY CODE ###

import itertools


def xORSum(arr, n):
    ans = 0
    for i in range(0, n):
        for j in range(i + 1, n):
            ans = ans + (arr[i] ^ arr[j])
    return ans


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

print(xORSum(a, n) % (10**9+7))


### FIXED CODE ###

import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))
mod = 10**9+7

ans = 0
max_digit = 0
for i in range(n):
    max_digit = max(max_digit, len(bin(a[i])))
for i in range(max_digit):
    num1 = np.count_nonzero((a >> i) & 1)  # 1の数
    num2 = n - num1  # 0の数
    ans += pow(2, i, mod) * (num1 * num2) % mod
print(ans % mod)
### BUGGY CODE ###

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

s=0

for i in range(N-K+1):
  s_=0
  for j in range(i,K+i):
  	s_+=p[j]
  if s_>s:
    s=s_
    
print((s+1*K)/2)

### FIXED CODE ###

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

s=sum(p[0:K])
d=0
e=0
for i in range(N-K):
  d+=p[i+K]-p[i]
  if d>e:
    e=d
s+=e
print((s+1*K)/2)
### BUGGY CODE ###

import sys
from collections import Counter, defaultdict, deque

sys.setrecursionlimit(2 * 10 ** 5)

(N,) = [int(x) for x in input().split()]
colors = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(N - 1)]
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)
parent = {1: None}
children = defaultdict(list)


def rootTree(node):
    for nbr in graph[node]:
        if nbr not in parent:
            parent[nbr] = node
            children[node].append(nbr)
            rootTree(nbr)


rootTree(1)


# cut tree into components that don't have a certain color
# if curr node is color c, each child that isn't color c forms a c-less component.
# Number of c-less path is size * (size + 1) / 2

colorlessCount = defaultdict(int)
colorlessComps = {}
for c in range(1, N + 1):
    colorlessComps[c] = [[]]


def buildComps(node):
    # Grow every colorless comp except for current color
    currColor = colors[node - 1]
    for c in colorlessComps:
        if c != currColor:
            colorlessComps[c][-1].append(node)
    for child in children[node]:
        colorlessComps[currColor].append([])
        buildComps(child)
        temp = colorlessComps[currColor].pop()
        s = len(temp)
        # print('size of colorless', currColor, ' is size', s, 'containing', temp)
        colorlessCount[currColor] += s * (s + 1) // 2


buildComps(1)
# print(colorToComps)
for c in colorlessComps:
    assert len(colorlessComps[c]) == 1
    temp = colorlessComps[c][0]
    s = len(temp)
    # print('size of root colorless', c, ' is size', s, 'containing', temp)
    colorlessCount[c] += s * (s + 1) // 2
# print(colorlessCount)
maxPairs = N * (N + 1) // 2
for c in range(1, N + 1):
    print(maxPairs - colorlessCount[c])


### FIXED CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(2 * 10 ** 5)

(N,) = [int(x) for x in input().split()]
colors = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(N - 1)]
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)
parent = {1: None}
children = defaultdict(list)


def rootTree(node):
    for nbr in graph[node]:
        if nbr not in parent:
            parent[nbr] = node
            children[node].append(nbr)
            rootTree(nbr)


rootTree(1)


colorlessCount = [0 for c in range(N + 1)]
colorlessTime = [0 for c in range(N + 1)]
t = 0


def buildComps(node):
    global t
    t += 1
    currColor = colors[node - 1]
    colorlessTime[currColor] += 1
    for child in children[node]:
        oldCount = t - colorlessTime[currColor]
        colorlessTime[currColor] = t
        buildComps(child)
        s = t - colorlessTime[currColor]
        colorlessTime[currColor] = t - oldCount
        colorlessCount[currColor] += s * (s + 1) // 2


buildComps(1)

for c in range(1, N + 1):
    s = t - colorlessTime[c]
    colorlessCount[c] += s * (s + 1) // 2
maxPairs = N * (N + 1) // 2
for c in range(1, N + 1):
    print(maxPairs - colorlessCount[c])
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))

    ans = 0
    from collections import Counter
    cnt = Counter(a)
    tmp = [0] * (max(a) + 1)
    set_a = list(set(a))
    set_a.sort()

    for aa in set_a:
        if tmp[aa] == 0:
            for j in range(aa,max(a)+1,aa):
                tmp[j] = 1

            if cnt[aa] == 1:
                # print(aa, ans)
                ans += 1




    print(ans)

if __name__=='__main__':
    main()


### FIXED CODE ###

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)
### BUGGY CODE ###

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

l = ''

while len(l) < N:
    for i in range(A):
        l += 'b'
    for i in range(B):
        l += 'r'

ln = l[:N]

ans = ln.count('b')

print(ans)

### FIXED CODE ###

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

sumAB = A + B
c = N // sumAB
k = N % sumAB
if k < A:
    ans = A * c + k
else:
    ans = A * c + A

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

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,M = inpl()
s = list(input())

'''
A
1 ~ N -> mod0
N+1 ~ 2N -> mod1

B
1 ~ N -> mod2
N+1 ~ 2N -> mod3
'''

lines = defaultdict(set)
for _ in range(M):
    a,b = inpl()
    a-=1
    b-=1
    sa, sb = s[a], s[b]
    if sa == sb:
        lines[a].add(b+N)
        lines[b].add(a+N)
    else:
        lines[a+N].add(b)
        lines[b+N].add(a)

ed = [0]*(2*N)
ans = False

def dfs(s):
    global ed
    if ed[s] == 1: #今訪れている
        print('Yes')
        sys.exit()
    elif ed[s] == 2: #昔訪れた
        return
    else: #まだ
        ed[s] = 1
        for t in lines[s]:
            dfs(t)
        ed[s] = 2

tmp = 0
for s in range(2*N):
    if ed[s] == 0:
        dfs(s)

print('No')


### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**8)

N,M = map(int, input().split())
s = list(input())

'''
A
1 ~ N -> mod0
N+1 ~ 2N -> mod1

B
1 ~ N -> mod2
N+1 ~ 2N -> mod3
'''

lines = [[] for i in range(2*N)]
for _ in range(M):
    a,b = map(int, input().split())
    a-=1
    b-=1
    sa, sb = s[a], s[b]
    if sa == sb:
        lines[a].append(b+N)
        lines[b].append(a+N)
    else:
        lines[a+N].append(b)
        lines[b+N].append(a)

ed = [0]*(2*N)

def dfs(s):
    global ed
    ed[s] = 1
    for t in lines[s]:
        if ed[t] == 1: #今訪れている
            print('Yes')
            sys.exit()
        elif ed[t] == 0:
            dfs(t)
    ed[s] = 2

for s in range(N):
    if ed[s] == 0:
        dfs(s)

print('No')
### BUGGY CODE ###

n, m = [int(i) for i in input().split()]
dp_prev = [float("inf") for i in range(2**n)]
dp_next = [float("inf") for i in range(2**n)]
dp_prev[0] = 0

for i in range(m):
    a, _ = [int(_) for _ in input().split()]
    c = sum([2**(int(_)-1) for _ in input().split()])

    for j in range(2**n):
        dp_next[j|c] = min(dp_prev[j|c], dp_prev[j] + a, dp_next[j|c])
        dp_next[j] = min(dp_prev[j], dp_next[j])
    dp_prev = dp_next[:]


print([dp_next[-1], -1][dp_next[-1] == float("inf")])


### FIXED CODE ###

n, m = [int(i) for i in input().split()]
dp = [[float("inf") for i in range(2**n)] for j in range(m+1)]
dp[0][0] = 0

for i in range(m):
    a, _ = [int(_) for _ in input().split()]
    c = sum([2**(int(_)-1) for _ in input().split()])

    for j in range(2**n):
        dp[i+1][j|c] = min(dp[i][j|c], dp[i][j] + a, dp[i+1][j|c])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])

print([dp[-1][-1], -1][dp[-1][-1] == float("inf")])
### BUGGY CODE ###

N = int(input())
S = str(input())

count = 0

for i in range (0, N-2):
  colour1 = S[i]
  for j in range (i+1, N-1):
    colour2 = S[j]
    if colour1 == colour2:
      continue
    else:
      for k in range(j+1, N):
        colour3 = S[k]
        if j-i == k-j:
          continue
        elif colour1 != colour3 and colour2 != colour3:
          count+=1
        else:
          continue

print(count)

### FIXED CODE ###

N = int(input())
S = str(input())

count = S.count('R')*S.count('G')*S.count('B')

for i in range (0, N-2):
  colour1 = S[i]
  for j in range (i+1, N-1):
    colour2 = S[j]
    if colour1 == colour2:
      continue
    else:
      if 2*j-i > N-1:
        continue
      elif colour1 != S[2*j-i] and colour2 != S[2*j-i]:
          count-=1
      else:
          continue

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

n, m, *ab = [int(x) for x in open(0).read().split()]

from_1, to_n = [], []
for a, b in zip(*[iter(ab)] * 2):
    if a == 1: from_1.append(b)
    elif b == n: to_n.append(a)
for b in from_1:
    if b in to_n: print('POSSIBLE'); exit()
print('IMPOSSIBLE')

### FIXED CODE ###

n, m, *ab = map(int, open(0).read().split())
from_1, to_n = set(), set()
for a, b in zip(*[iter(ab)] *2):
    if a == 1: from_1.add(b)
    if b == n: to_n.add(a)
print('POSSIBLE' if from_1 & to_n else "IMPOSSIBLE")
### BUGGY CODE ###

N,K = map(int,input().split())
A = [int(i) for i in input().split()]

counter = 0
d = {}
types = list(set(A))

for i in range(len(types)):
    d[str(types[i])] = A.count(types[i])


for i in range(len(d)-K):
    minKey = min(d, key=d.get)
    counter += d[minKey]
    del d[minKey]

'''
while len(d) > K:
    minKey = min(d, key=d.get)
    counter += d[minKey]
    del d[minKey]
'''
print(counter)




### FIXED CODE ###

from collections import Counter

N,K = map(int,input().split())
A = [i for i in input().split()]

altCounter = 0
d = Counter(A).most_common()
d = d[::-1]

for i in range(len(d)-K):
    altCounter += d[i][1]

print(altCounter)
### BUGGY CODE ###

def main():
    import collections

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

    balls_dict = collections.Counter(balls)

    for ball in balls:
        answer = 0
        for num, quantity in balls_dict.items():
            if num == ball:
                answer += (quantity-2) * (quantity-1) // 2
            else:
                answer += quantity * (quantity-1) // 2

        print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import collections

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

    balls_dict = collections.Counter(balls)
    num_patterns = 0
    for value in balls_dict.values():
        num_patterns += value * (value-1) // 2

    for ball in balls:
        print(num_patterns - balls_dict[ball] + 1)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, C = map(int, input().split())

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

ans = 0
for a in range(N+1):
    for b in range(a+1, N+2):
        # O -> A -> B
        a1 = sV[a]+sV[-1]-sV[b-1]-2*X[a]-(C-X[b])

        # O -> B -> A
        a2 = sV[a]+sV[-1]-sV[b-1]-X[a]-2*(C-X[b])

        ans = max(ans, a1, a2)

print(ans)


### FIXED CODE ###

N, C = map(int, input().split())

X = [0]
V = [0]
sV = [0]
Amax1 = [0]
Amax2 = [0]
for _ in range(N):
    x, v = map(int, input().split())
    X.append(x)
    V.append(v)
    sV.append(sV[-1]+v)
    Amax1.append(max(Amax1[-1], sV[-1]-x))
    Amax2.append(max(Amax2[-1], sV[-1]-2*x))
X.append(C)

ans = 0
for b in range(1, N+2):
    # O -> A -> B
    a1 = Amax2[b-1]+sV[-1]-sV[b-1]-(C-X[b])

    # O -> B -> A
    a2 = Amax1[b-1]+sV[-1]-sV[b-1]-2*(C-X[b])

    ans = max(ans, a1, a2)

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

n = int(input())
#a = list(map(int,input().split()))
a = input()
q = int(input())
for i in range(q):
    b,c = input().split()
    a = a.replace(b,c)
    al = list(map(int,a.split()))
    #print(al,type(al))
    su = sum(al)
    print(su)
    

### FIXED CODE ###

from collections import Counter

n = int(input())
a = list(map(int,input().split()))
q = int(input())
freq = Counter(a)
sm = sum(a)
for i in range(q):
    b,c = map(int,input().split())
    bn = freq[b]
    freq[b] = 0
    if c in freq:
        freq[c] += bn
    else:
        freq[c] = bn
    sm = sm + (c-b)*bn
    print(sm)
### BUGGY CODE ###

n, k = map(int, input().split(" "))
h = [int(i) for i in input().split(" ")]

dp = [0] * n

for i in range(1, n, 1):
  candidate = []
  for j in range(min(i, k)) :
    candidate.append(dp[i - j - 1] + abs(h[i - j -1] - h[i]))
  dp[i] = min(candidate)

print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split(" "))
h = [int(i) for i in input().split(" ")]

dp = [0] * n

for i in range(1, n, 1):
  candidate = []
  for j in range(min(i, k)) :
    candidate.append(dp[i - j - 1] + abs(h[i - j -1] - h[i]))
  dp[i] = min(candidate)

print(dp[n-1])