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

import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
monster = {}
x = []
for i in range(n):
    xx, hh = MAP()
    monster[xx] = hh
    x.append(xx)
x.sort()
cnt = 0
for i in range(n):
    cx, ch = x[i], monster[x[i]]
    if ch <= 0:
        continue
    cn = (ch + a - 1) // a
    cnt += cn
    tmp = []
    j = i + 1
    while j < n:
        nx = x[j]
        if nx <= cx + 2*d:
            if monster[nx] > 0:
                monster[nx] -= cn * a
            j += 1
        else:
            break
    
print(cnt)

### FIXED CODE ###

from collections import deque
import sys

input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]

xh = sorted(xh, key=lambda x:(x[0]))
q = deque()
ca = 0
cnt = 0
for i in range(n):
    cx, ch = xh[i][0], xh[i][1]
    
    while q and q[0][0] < cx:
        qx, qa = q.popleft()
        ca -= qa
    
    if ch - ca <= 0:
        continue
    
    cn = (ch - ca + a - 1) // a
    cnt += cn
    ca += cn * a
    q.append([cx+2*d, cn*a])
    
print(cnt)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
res = []
for i in range(N):
    res.append(L[i])
    res.reverse()
for i in range(N):
    print(str(res[i]) + ' ', end="")

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
L.reverse()
lim = int(N/2)
if N%2 == 0:
    for i in range(lim):
        print(str(L[2*i]) + ' ', end="")

    L.reverse()
    for i in range(int(N/2)):
        print(str(L[2*i]) + ' ', end="")
else:
    lim += 1
    for i in range(lim):
        print(str(L[2*i]) + ' ', end="")

    L.reverse()
    for i in range(int(N/2)):
        print(str(L[2*i+1]) + ' ', end="")
### BUGGY CODE ###


import sys
sys.setrecursionlimit(1000000)

# 壊れている床を無視すればフィボナッチ数になってる
from collections import defaultdict

def Fib(n, dd, broken):
    if n in broken:
        return 0

    if dd[n] != 0:
        return dd[n]

    if n <= 1:
        return 1

    x = Fib(n-1, dd, broken) + Fib(n-2, dd, broken)
    dd[n] = x
    return x

dd = defaultdict(int)

n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]

ans = Fib(n, dd, A)
print(ans % 1000000007)

### FIXED CODE ###


# 壊れている床を無視すればフィボナッチ数になってる
from collections import defaultdict

def Fib(n, broken):
    dd = defaultdict(int)

    dd[0] = 1

    for i in range(n):
        for j in range(i+1, min(n, i+2)+1):
            if broken[j] == 0:
                dd[j] += dd[i]
                dd[j] %= 1000000007

    return dd[n]


n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]
broken = defaultdict(int)
for c in A:
    broken[c] = 1

ans = Fib(n, broken)
print(ans % 1000000007)
### BUGGY CODE ###

import collections

def add(c):
    return sum([int(k)*int(v) for k, v in c.items()])

n = int(input())
a = [int(each) for each in input().split()]
q = int(input())
rep = [tuple(int(each) for each in input().split()) for i in range(q)]

s = [str(sum(a))]

c = collections.Counter(a)
for i in range(q):
    # 存在しないときにエラーになる
    if c.get(rep[i][0]):
        c[rep[i][1]] += c.pop(rep[i][0])
    s.append(add(c))
print('\n'.join([str(each) for each in s[1:]]))

### FIXED CODE ###

import collections

n = int(input())
a = [int(each) for each in input().split()]
q = int(input())
rep = [tuple(int(each) for each in input().split()) for i in range(q)]

s = [sum(a)]

c = collections.Counter(a)
for i in range(q):
    diff = (rep[i][1]-rep[i][0])
    num = c.get(rep[i][0])
    if not num:
        num = 0
    # print('i:', i)
    # print(c)
    # print('差分:', diff, '個数:', num)
    s.append(s[-1]+num*diff)

    # 存在しないときにエラーになる
    if c.get(rep[i][0]):
        c[rep[i][1]] += c.pop(rep[i][0])

print('\n'.join([str(each) for each in s[1:]]))
### BUGGY CODE ###

#dp[i+1][j+1]:=Sのi文字目までとTのj文字目までのLCSの長さ
S=input()
T=input()
ls=len(S)
lt=len(T)

dp=[["" for j in range(lt+1)] for i in range(ls+1)]

for i in range(ls):
    for j in range(lt):
        if S[i]==T[j]: 
            dp[i+1][j+1]=max(dp[i][j]+S[i],dp[i+1][j],dp[i][j+1],key=len)
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1],key=len)
print(dp[ls][lt])


### FIXED CODE ###

s = input()
t = input()
ls = len(s)
lt = len(t)


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ''

for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])


i = ls-1
j = lt-1
while (0 <= i) & (0 <= j):
    if s[i] == t[j]:
        answer += s[i]
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        i -= 1
if len(answer) == 0:
  print('')
else:
  print(answer[::-1])
### BUGGY CODE ###

def gcd(a,b):
    if a%b == 0:
        return b
    else:
        return gcd(b,a%b)

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

a = sorted(list(set(a)))

owa = 0
saiko = a[0]//2

for i in range(1,len(a)):
    t1 = a[i]//2
    koe = gcd(saiko,t1)
    saiko = (saiko*t1)//koe

for i in range(len(a)):
    check = saiko//(a[i]//2)
    if check%2 == 0:
        owa = 1
        
if owa == 1:
    print(0)
else:
    if (M//saiko)%2 == 0:
        print((M//saiko)//2 )
    else:
        print(((M//saiko)+1)//2)



### FIXED CODE ###

def gcd(a,b):
    if a%b == 0:
        return b
    else:
        return gcd(b,a%b)

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

a = sorted(list(set(a)))
b = [a[i]//2 for i in range(len(a))]

owa = 0
saiko = b[0]

for i in range(1,len(a)):
    t1 = b[i]
    koe = gcd(saiko,t1)
    saiko = (saiko*t1)//koe
    if (saiko//b[i])%2 == 0:
        break

for i in range(len(a)):
    check = saiko//(b[i])
    if check%2 == 0:
        owa = 1
        break

if owa == 1:
    print(0)
else:
    if (M//saiko)%2 == 0:
        print((M//saiko)//2 )
    else:
        print(((M//saiko)+1)//2)
### BUGGY CODE ###

import sys
import array

from operator import itemgetter

def upd(ft,i):
	i+=1
	while(i<=len(ft)):
		ft[i]+=1
		i+=i&-i

def get(ft,i):
	i+=1
	ret=0
	while(i!=0):
	    ret+=ft[i]
	    i-=i&-i
	return ret


def comb(cnt,x):
	return cnt[x]-1;

def main():

	input = sys.stdin.readline
	tl=200100

	ft=[0]*tl


	md = 998244353
	n = int(input())
	xy = [[0]*2 for _ in range(n)]
	ys = []
	hp = []
	for i in range(n):
		xy[i] = [int(item) for item in input().split()]
	xy.sort(key=itemgetter(0))
	yxi = [y for x, y in xy]

	*YS, = set(yxi)
	YS.sort()
	yxi= list(map({e: i for i, e in enumerate(YS)}.__getitem__, yxi))

	ct=[0]*(n+1)
	ct[0]=1
	for i in range(1,n+1):
		ct[i]=ct[i-1]*2%md

	cnt=tuple(ct)

	def calc(ft,get,upd,cnt):
		for i, y in enumerate(yxi):
			v = get(ft,y+1); upd(ft,y+1)
			p1 = cnt[v]; p0 = cnt[y - v]
			q1 = cnt[i - v]; q0 = cnt[(n - y - 1) - (i - v)]
			yield (p0 + p1 + q0 + q1 - (p0 + q1) * (p1 + q0)) % md


	print((sum(calc(ft,get,upd,cnt))+n*cnt[n] - n)%md)

main()


### FIXED CODE ###

import sys
import array

from operator import itemgetter

def main():



	input = sys.stdin.readline


	md = 998244353
	n = int(input())
	tl=n+1
	
	ft=[0]*tl

	xy = [[0]*2 for _ in range(n)]
	for i in range(n):
		xy[i] = [int(item) for item in input().split()]
	xy.sort(key=itemgetter(0))
	yxi = [y for x, y in xy]

	*YS, = set(yxi)
	YS.sort()
	yxi= list(map({e: i for i, e in enumerate(YS)}.__getitem__, yxi))

	ct=[0]*(n+1)
	ct[0]=1
	for i in range(1,n+1):
		ct[i]=ct[i-1]*2%md

	cnt=tuple(ct)

	def upd(i):
		i+=1
		while(i<=n):
			ft[i]+=1
			i+=i&-i

	def get(i):
		i+=1
		ret=0
		while(i!=0):
		    ret+=ft[i]
		    i-=i&-i
		return ret

	def calc(get,upd):
		for i, y in enumerate(yxi):
			v = get(y); upd(y)
			p1 = cnt[v]; p0 = cnt[y - v]
			q1 = cnt[i - v]; q0 = cnt[(n - y - 1) - (i - v)]
			yield (p0 + p1 + q0 + q1 - (p0 + q1) * (p1 + q0)) % md


	print((sum(calc(get,upd))+n*cnt[n] - n)%md)

main()
### BUGGY CODE ###

d , g = map(int, input().split())
pc = [list(map(int, input().split()))for i in range(d)]
x=[]
y=[0]*d
def dfs(n,m,y,now):
    if now==n:
        z=y.copy()
        x.append(z)
        return
    for i in range(m):
        y[now]=i
        dfs(n,m,y,now+1)
dfs(d,3,y,0)

mi = 1000
for i in x:
    sum = 0
    cost = 0
    stock = []
    for j in range(d):
        if i[j]==1:
            sum+=pc[j][0]*(j+1)*100+pc[j][1]
            cost+=pc[j][0]
        if i[j]==2:
            stock+=[(j+1)*100]*pc[j][0]
    stock.sort()
    while sum<g and stock:
        sum+=stock.pop()
        cost+=1
    if sum>=g:
        mi=min(mi,cost)

print(mi)


### FIXED CODE ###

d , g = map(int, input().split())
pc = [list(map(int, input().split()))for i in range(d)]
x=[]
y=[0]*d
ac=[0]*d
for i in range(d):
    ac[i]=pc[i][0]*(i+1)*100+pc[i][1]

def dfs(n,m,y,now):
    if now==n:
        z=y.copy()
        x.append(z)
        return
    for i in range(m):
        y[now]=i
        dfs(n,m,y,now+1)
dfs(d,3,y,0)
mi = 1000
for i in x:
    sum = 0
    cost = 0
    stock = []
    sum2 = 0
    cost2 = 0
    for j in range(d):
        if i[j]==1:
            sum+=ac[j]
            cost+=pc[j][0]
            sum2+=ac[j]
            cost2+=pc[j][0]
        if i[j]==2:
            stock+=[(j+1)*100]*pc[j][0]
            sum2+=pc[j][0]*(j+1)*100
            cost2+=pc[j][0]
    if sum2<g:
        continue
    stock.sort()
    if abs(sum2-g)>abs(sum-g):
        while sum<g and stock:
            sum+=stock.pop()
            cost+=1
        if sum>=g:
            mi=min(mi,cost)
    else:
        while sum2>g and stock:
            sum2-=stock.pop()
            cost2-=1
        cost+=1
        mi=min(mi,cost2)

print(mi)
### BUGGY CODE ###

import sys
h,w,m = map(int,input().split())
H = [0]*(h)
W = [0]*(w)
ch = [[False]*w for _ in range(h)]
for _ in range(m):
    a,b = map(int,input().split())
    H[a-1] += 1
    W[b-1] += 1
    ch[a-1][b-1] = True
hm = max(H)
wm = max(W)
for i in range(len(H)):
    if H[i] != hm:
        continue
    for j in range(len(W)):
        if W[j] != wm:
            continue
        if ch[i][j] != True:
            print(hm+wm)
            sys.exit()
print(hm+wm-1)

            
        

### FIXED CODE ###

h,w,m = map(int,input().split())
x = {}
y = {}
dic = {}
for _ in range(m):
    a,b = map(int,input().split())
    dic[(a,b)] = 1
    x[a] = x.get(a,0) + 1
    y[b] = y.get(b,0) + 1
p = max(x.values())
q = max(y.values())
cnt = 1
a = [i for i in x if x[i] == p]
b = [j for j in y if y[j] == q]
for i in a:
    for j in b:
        if dic.get((i,j),-1) == -1:
            cnt = 0
            break
    if not cnt:
        break
print(p+q-cnt)
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()]
b = []
for i in range(N):
    if i % 2 == 0:
        b.append(a[i])
    else:
        b.insert(0, a[i])
if N % 2 == 1:
    b.reverse()
[print(b[i], end=' ') for i in range(len(b))]


### FIXED CODE ###

from collections import deque
N = int(input())
a = [int(i) for i in input().split()]
b = deque()
for i in range(N):
    if i % 2 == 0:
        b.append(a[i])
    else:
        b.appendleft(a[i])
if N % 2 == 1:
    [print(b[i], end=' ') for i in reversed(range(len(b)))]
else:
    [print(b[i], end=' ') for i in range(len(b))]
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
L = []
for n in range(Q):
    l, r = map(int, input().split())
    R = S[l-1:r]
    L.append(R.count("AC"))
for n in range(Q):
    print(L[n])

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
A = [0]*(N-1)
B = [0]
C = []
for n in range(N-1):
    if S[n:n+2] == "AC":
        A[n] += 1
for n in range(N-1):
    B.append(B[n]+A[n])
for n in range(Q):
    l, r = map(int, input().split())
    C.append(B[r-1]-B[l-1])
for n in range(Q):
    print(C[n])
### BUGGY CODE ###

class DisjointSet():
    def __init__(self, n):
        self._p = [x for x in range(n)]
        self._size = [-1 for x in range(n)]
    
    def find(self, p):
        return self._p[p]
    
    def union(self, p, q):
        pp, qq = self.find(p), self.find(q)
        sp, sq = self._size[pp], self._size[qq]
        if pp != qq:
            for i in range(len(self._p)):
                if self._p[i] == pp:
                    self._p[i] = qq
            self._size[qq] += self._size[pp]
    
    def size(self, p):
        return self._size[self.find(p)]


n, m = [int(x) for x in input().split()]
b =  [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
b.reverse()
r = []
t = n*(n-1)//2
ds = DisjointSet(n)
for q, p in b:
  r.append(t)
  qq, pp = ds.find(p), ds.find(q)
  if pp != qq:
    t -= ds.size(pp) * ds.size(qq)
  ds.union(p, q)
for x in reversed(r):
  print(x)

### FIXED CODE ###

class Unionfind():
    def __init__(self, progsize):
        self.table = [-1 for _ in range(progsize)]
        self.size = [1 for _ in range(progsize)]

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

    def union(self, x, y):
        xl = self.find(x)
        yl = self.find(y)
        if xl != yl:
            if self.table[xl] <= self.table[yl]:
                self.table[yl] = xl
                self.table[xl] -= 1
                self.size[xl] += self.size[yl]
            else:
                self.table[xl] = yl
                self.table[yl] -= 1
                self.size[yl] += self.size[xl]

n, m = map(int, input().split())
bridge = [tuple(map(int, input().split())) for _ in range(m)]
bridge.reverse()
uf = Unionfind(n)
cur = n * (n-1) // 2
ans = [cur]
for a, b in bridge:
    ap = uf.find(a-1)
    bp = uf.find(b-1)
    if ap != bp:
        cur -= uf.size[ap] * uf.size[bp]
    uf.union(a-1, b-1)
    ans.append(cur)
for a in reversed(ans[0:m]):
    print(a)
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
a = map(int, input().split())
a = sorted(a)
for i in range(m):
  a[-1] = int(a[-1] / 2)
  tmp = a[:-1]
  p = bisect.bisect_left(tmp, a[-1])
  a = tmp[:p] + [a[-1]] + tmp[p:]
print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

for i in range(m):
  tmp = int(heapq.heappop(a) / 2)
  heapq.heappush(a, tmp)
print(-1 * sum(a))
### BUGGY CODE ###

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

Ls.sort()
S = 0
for i in range(N - 2):
    A = Ls[i]
    for j in range(i + 1, N - 1):
        B = Ls[j]
        for k in range(j + 1, N):
            C = Ls[k]
            if A + B <= C:
                break
            else:
                S += 1
print(S)


### FIXED CODE ###

import bisect

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

Ls.sort()
S = 0
for i in range(N - 2):
    A = Ls[i]
    for j in range(i + 1, N - 1):
        B = Ls[j]
        k = bisect.bisect_left(Ls, A + B, j + 1)
        S += k - j - 1
print(S)
### BUGGY CODE ###

import math
from functools import reduce
answer=0

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K=int(input())
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            #print(i,j,k)
            answer+=gcd(i,j,k)
                
                
print(answer)

### FIXED CODE ###

import math
from functools import reduce
answer=0
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
K=int(input())
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            #print(i,j,k)
            answer+=gcd(i,j,k)
                
                
print(answer)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    F=list(map(int,input().split()))
    F.sort(reverse=True)
    A.sort()
    right=10**12
    left=-1
    while right-left>1:#区間(left,right]に解Xがある
        x=(right+left)//2
        k_sum=0
        for i in range(n):
            k_sum+=max(0,A[i]-x//F[i])
        if k_sum<=k:
            right=x
        else:
            left=x
    print(right)
    

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    F=list(map(int,input().split()))
    F.sort(reverse=True)
    A.sort()
    right=10**12
    left=-1
    while right-left>1:#区間(left,right]に解Xがある
        x=(right+left)//2
        k_sum=0
        for i in range(n):
            k_sum+=max(0,A[i]-x//F[i])
        if k_sum<=k:
            right=x
        else:
            left=x
    print(right)
    

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

import re
s = input()
replaced = -1
c = 0

while replaced != 0:
    s, replaced = re.subn("BW", "WB", s)
    c += replaced

print(c)

### FIXED CODE ###

s = input()

b = 0
c = 0
for i in range(len(s)):
    if s[i] == "B":
        b += 1
    else:
        c += b

print(c)
### BUGGY CODE ###

import numpy as np
from copy import deepcopy 

n,p = map(int, input().split())
s = list(map(int, input().strip()))

zero = np.zeros(p,dtype = int) #動的計画法
dp = deepcopy(zero)

count = 0
d = 1
for i in range(n): #1の位から順に数を追加していく
    ne_ar = deepcopy(zero)
    if(p == 2 or p == 5): #10と互いに素ではない場合
        ne = int(s[n-i-1]) % p
        if(ne == 0):
            dp[0] += 1
        count += dp[0] #
    else:
        ne = (int(s[n-i-1]) * d) % p #10とは互いに素なので、sと同じ位で考えて良い
        ne_ar[ne:] += dp[:(p-ne)] #新しく追加する数の余りをずらす
        ne_ar[:ne] += dp[(p-ne):]
        ne_ar[ne] += 1 #新しい数のみの時
        dp = ne_ar
        d *= 10
        d %= p
        count += ne_ar[0] #neを一番上の位とする部分集合の数を足す

print(count)


### FIXED CODE ###

n,p = map(int, input().split())
s = list(map(int, input().strip()))

count = 0

if(p == 2 or p == 5): #10と互いに素ではない場合
    co = 0
    for i in range(n): #1の位から順に数を追加していく
        ne = int(s[n-i-1]) % p
        if(ne == 0):
            co += 1
        count += co
    print(count)
else:
    sta = [0]*p
    sta[0] += 1
    d = 1
    co = 0
    for i in range(n):
        ne = int(s[n-i-1]) * d % p
        co += ne
        co %= p
        sta[co] += 1
        d *= 10
        d %= p
    for i in range(p):
        count += sta[i] * (sta[i]-1) // 2
    print(count)
### BUGGY CODE ###

n = int(input())
a_lst = list(map(int, input().split()))
x = 10 ** 18
ans = 1
for i in range(n):
    ans *= a_lst[i]

if ans > x:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

# import numpy as np
n = int(input())
a_lst = list(map(int, input().split()))
x = 10 ** 18

# ans = np.prod(a_lst)



ans = 1
if 0 in a_lst:
    # print("a")
    ans = 0
else:
    for i in range(n):
        ans *= a_lst[i]
        if ans > x:
            ans = -1
            break
        # elif ans == 0:
        #     break
    
# if ans > x:
#     print(-1)
# else:
#     print(ans)
print(ans)
### BUGGY CODE ###

s=input()
q= int(input())
 
for iq in range(1,q+1):
	t=input().split()
	if t[0]=='1':
		s=s[::-1]
	else:
		if t[1]=='1':
			s=t[2]+s
#			s=f"{t[2]}{s}"
#			list1=[t[2],s]
#			s="".join(list1)
		else:
			s=s+t[2]
#			s=f"{s}{t[2]}"   
#			list2=[s,t[2]]
#			s="".join(list2)
 
print (s)


### FIXED CODE ###

s=input()
q= int(input())

top=""
btm=""

iturn=0
for iq in range(1,q+1):
	t=input().split()
	if t[0]=='1':
		iturn=iturn+1   	
	else:
		iturn2=iturn%2
		if (t[1]=='1' and iturn2==0) or (t[1]=='2' and iturn2==1):
#			s=t[2]+s
#			s='{}{}'.format(t[2],s)
			top=t[2]+top
		else:
#			s=s+t[2]
#			s='{}{}'.format(s,t[2])
			btm=btm+t[2]

if iturn%2==0:
	s=top+s+btm
else:
	s=btm[::-1]+s[::-1]+top[::-1]
print (s)
### BUGGY CODE ###

import bisect

N = int(input())
A = list(map(int, input().split()))
accum = [0 for i in range(N + 1)]
for i in range(N):
    accum[i + 1] = accum[i] + A[i]
#accum[i + 1] = A[0] + A[1] + ... + A[i]
#sum(A[i:j]) = A[i] + A[i+1] + ... + A[j-1] = accum[j] - accum[i]
ans = float('inf')
for i in range(2, N - 1, 1): #2番目の区切りを A[i-1]とA[i]の間に入れる
    zenhan = accum[i] #(= sum(A[:i]))
    kouhan = accum[N] - accum[i]#(= sum(A[i:N]))
    index1l = bisect.bisect(accum, zenhan // 2, lo = 2, hi = i) - 1
    index1r = min(index1l + 1, i - 1)
    index3l = bisect.bisect(accum, zenhan + (kouhan // 2), lo = i + 2, hi = N) - 1
    index3r = min(index3l + 1, N - 1)
    for index1 in (index1l, index1r):
        for index3 in (index3l, index3r):
            B, C, D, E = accum[index1], accum[i] - accum[index1], accum[index3] - accum[i], accum[N] - accum[index3]
            M = max(B, C, D, E)
            m = min(B, C, D, E)
            ans = min(ans, M - m)
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
A = list(map(int, input().split()))
accum = [0 for i in range(N + 1)]
for i in range(N):
    accum[i + 1] = accum[i] + A[i]
total = accum[N]
#accum[i + 1] = A[0] + A[1] + ... + A[i]
#sum(A[i:j]) = A[i] + A[i+1] + ... + A[j-1] = accum[j] - accum[i]
ans = float('inf')
for i in range(2, N - 1, 1): #2番目の区切りを A[i-1]とA[i]の間に入れる
    zenhan = accum[i] #(= sum(A[:i]))
    kouhan = total - zenhan #(= accum[N] - accum[i] = sum(A[i:N]))
    index1l = bisect.bisect(accum, zenhan // 2, lo = 2, hi = i) - 1
    index1r = min(index1l + 1, i - 1)
    index3l = bisect.bisect(accum, zenhan + (kouhan // 2), lo = i + 2, hi = N) - 1
    index3r = min(index3l + 1, N - 1)
    for index1 in (index1l, index1r):
        for index3 in (index3l, index3r):
            B, C, D, E = accum[index1], zenhan - accum[index1], accum[index3] - zenhan, total - accum[index3]
            M = max(B, C, D, E)
            m = min(B, C, D, E)
            ans = min(ans, M - m)
print(ans)
### BUGGY CODE ###

INF = 10**9

n, k = list(map(int, input().split(' ')))
hs = list(map(int, input().split(' ')))

dp = [INF] * n
dp[0] = 0

for i in range(1, n):
    l = min([i, k])
    for m in range(1, l + 1):
        v = dp[i - m] + abs(hs[i - m] - hs[i])
        if dp[i] > v:
            dp[i] = v

print(dp[-1])


### FIXED CODE ###

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

hs = list(map(int, input().split(' ')))

dp = [float('inf')] * (n + k + 1)
dp[0] = 0

for i in range(n - 1):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i + j] = min([
                dp[i + j],
                dp[i] + abs(hs[i] - hs[i + j])
            ])

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

from math import factorial
import bisect

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

lst = sorted(lst)

def nCr(n,r):
    return factorial(n)/factorial(n-r) * factorial(r)

if n == 2:
    print(max(lst), min(lst))
else:
    num = max(lst)
    r1 = bisect.bisect_left(lst, num//2)
    r2 = bisect.bisect_right(lst, num//2)
    
    val1 = nCr(num, lst[r1])
    val2 = nCr(num, lst[r2])
    
    if val1 >= val2:
        ans = (max(num, lst[r1]), min(num, lst[r1]))
    else:
        ans = (max(num, lst[r2]), min(num, lst[r2]))
    
    print(*ans)

### FIXED CODE ###

n = int(input())
lst = list(map(int,input().split()))
lst.sort()

m = lst[-1]
line = m / 2
r = 10**10

for i in range(n):
    if abs(r-line) > abs(lst[i]-line):
        r = lst[i]
print(m,r)
### BUGGY CODE ###

h,w,d = map(int,input().split())
dic = {}

for y in range(h):
    line = list(map(int,input().split()))
    for x in range(w):
        num = line[x]
        dic[num] = (x,y)

Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    cst = 0
    while l != r:
        (x,y) = dic[l]
        (nx,ny) = dic[l+d]
        cst += abs(nx - x) + abs(ny - y)
        l += d
    print(cst)

### FIXED CODE ###

h,w,d = map(int,input().split())
dic = {}

for y in range(h):
    line = list(map(int,input().split()))
    for x in range(w):
        num = line[x]
        dic[num] = (x,y)

com_sum = [0]*(h*w + 1)

for n in range(1,d+1):
    com_sum[n] = 0
    while n+d <= h*w:
        nx,ny = dic[n+d]
        x,y = dic[n]
        com_sum[n+d] = com_sum[n] + abs(nx-x) + abs(ny-y)
        n += d
    
Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    print(com_sum[r] - com_sum[l])