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

class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod


def main():
    mod = 10 ** 9 + 7
    ncr = nCrMod(mod)

    r1, c1, r2, c2 = map(int, input().split())
    r1, c1 = r1 - 1, c1 - 1
    t = ncr(r2 + c2 + 2, c2 + 1) + ncr(r1 + c1 + 2, c1 + 1) - ncr(r1 + c2 + 2, c2 + 1) - ncr(r2 + c1 + 2, c1 + 1)
    print(t % mod)

main()


### FIXED CODE ###

class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod


def main():
    mod = 10 ** 9 + 7
    ncr = nCrMod(mod)

    r1, c1, r2, c2 = map(int, input().split())
    r1, c1 = r1 - 1, c1 - 1
    t = ncr(r2 + c2 + 2, c2 + 1) + ncr(r1 + c1 + 2, c1 + 1) - ncr(r1 + c2 + 2, c2 + 1) - ncr(r2 + c1 + 2, c1 + 1)
    print(t % mod)

main()
### BUGGY CODE ###

a, b, c, k = list(map(int,input().strip().split()))
ans = int(0)
for i in range(k):
    if a > 0:
        ans += 1
        a -= 1
    elif b > 0:
        b -= 1
    else:
        ans -= 1
        c -= 1
print(ans)

### FIXED CODE ###

a, b, c, k = list(map(int,input().strip().split()))
ans = int(0)
if k >= a:
    ans += a
    k -= a
else:
    ans += k
    k = 0
if k >= b:
    k -= b
if k >= c:
    ans -= c
else:
    ans -= k
print(ans)
### BUGGY CODE ###

N = int(input())
a_list = list(map(int, input().split()))
result_str = ''

for i in range(1, N+1):
    result_str += str(a_list.count(i)) + '\n'

# 最後の改行を削除
result_str = result_str[:-1]
print(result_str)


### FIXED CODE ###

N = int(input())
a_list = list(map(int, input().split()))
result_list = [0] * N

for a in a_list:
    result_list[a-1] += 1

result_list_str = [str(i) for i in result_list]
print('\n'.join(result_list_str))
### BUGGY CODE ###

x=int(input())
A=[]
C=[]
for i in range(100000):
    A.append((i)**5)
    C.append((-(i))**5)
for i in range(len(A)):
    for j in range(len(A)):
        if x==A[i]-A[j]:
            print(i,j)
            #print(A[i],A[j])
            #print(A)
            exit()
        elif x==A[i]-C[j]:
            print(i,-(j))
            #print(A[i],C[j])
            #print(C)
            exit()

            
    


### FIXED CODE ###

x=int(input())
A=[]
C=[]
for i in range(100000):
    A.append((i)**5)
    C.append((-(i))**5)
for i in range(len(A)):
    for j in range(len(A)):
        if x==A[i]-A[j]:
            print(i,j)
            #print(A[i],A[j])
            #print(A)
            exit()
        elif x==A[i]-C[j]:
            print(i,-(j))
            #print(A[i],C[j])
            #print(C)
            exit()
### BUGGY CODE ###

S = list(input())

count = 0
i = 0
while i < len(S)-1:
    if S[i]=='B' and S[i+1]=='W':
        S[i]='W'
        S[i+1]='B'
        count += 1
        if i > 0:
            i -= 1
        else:
            i += 1
    else:
            i += 1
print(count)


### FIXED CODE ###

S = input()

count = 0
black = 0
white = 0

for i in range(len(S)-1):
    if S[i] == 'B':
        black +=1
    else :
        white +=1
    if  S[i+1] == 'W':
        count += i+1 -white

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

times = int(input())
count = 0
nums = list(map(int, input().split()))
total = 1

while count < times:
    total = total * nums[count]
    count += 1

if total < 1000000000000000001:
    print(total)
else:
    print(-1)

### FIXED CODE ###

def main():
    n = int(input())
    l = list(map(int, input().split(' ')))
    l.sort()
    if l[0] == 0:
        print(0)
        return
    
    total = 1

    for i in l:
        total = total * i
        if (total > 1000000000000000000):
            print(-1)
            return
    
    print(total)

main()
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
S = [c for c in S]
total = [0]*N
cnt = 0

flag = False
for i in range(N):
    if flag:
        if S[i]=='C':
            cnt += 1
        flag = False
    else:
        if S[i]=='A':
            flag = True
    total[i] = cnt

for _ in range(Q):
    l, r = map(int, input().split())
    s = total[l-1:r]
    print(s[-1]-s[0])

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

total = [0]*(N+1)
for i in range(2, N+1):
    if S[i-2]=='A' and S[i-1]=='C':
        total[i] = total[i-1]+1
    else:
        total[i] = total[i-1]

for i in range(Q):
    l, r = map(int, input().split())
    print(total[r]-total[l])
### BUGGY CODE ###

H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1

S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [10**7]*((W+4)*(H+4))
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque
d = deque()
visited[sh*(W+4)+sw] = 0
d.append(sh*(W+4)+sw)

while len(d)>0:
  a = d.popleft()
  h,w = divmod(a,W+4)
  cnt = visited[a]
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    a1 = h1*(W+4)+w1
    if S[h1][w1]=='.':
      if visited[a1]>cnt:
        visited[a1]=cnt
        d.append(a1)
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    a2 = h2*(W+4)+w2
    if S[h2][w2]=='.':
      if visited[a2]>cnt+1:
        visited[a2]=cnt+1
        d.append(a2)
ans = visited[gh*(W+4)+gw] if visited[gh*(W+4)+gw]<10**7 else -1
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1
s = sh*(W+4)+sw
g = gh*(W+4)+gw
S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [10**7]*((W+4)*(H+4))
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque

d = deque()
visited[s] = 0
d.append(s)
ans = 10**8
while len(d)>0:
  a = d.popleft()
  h,w = divmod(a,W+4)
  cnt = visited[a]
  if ans<=cnt:
    continue
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    a1 = h1*(W+4)+w1
    if (h1,w1)==(gh,gw):
      ans = min(ans,cnt)
    if S[h1][w1]=='.':
      if visited[a1]>cnt:
        visited[a1]=cnt
        d.appendleft(a1)
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    a2 = h2*(W+4)+w2
    if (h2,w2)==(gh,gw):
      ans = min(ans,cnt+1)
    if S[h2][w2]=='.':
      if visited[a2]>cnt+1:
        visited[a2]=cnt+1
        d.append(a2)
if ans==10**8:
  ans = -1
print(ans)
### BUGGY CODE ###

import heapq
import sys
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    a = [input().strip() for i in range(H)]

    INF = int(1e8)
    min_cost = [[INF] * W for i in range(H)]

    q = []
    for y in range(H):
        for x in range(W):
            if a[y][x] == "#":
                heapq.heappush(q, (0, x, y))
    
    ans = 0
    while len(q) > 0:
        cost, x, y = heapq.heappop(q)
        # 最小コストでテーブルを更新
        if cost < min_cost[y][x]:
            ans = max(ans, cost)
            min_cost[y][x] = cost
            for nx, ny in [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]:
                if 0 <= nx and nx < W and 0 <= ny and ny < H:
                    if cost + 1 < min_cost[ny][nx]:
                        heapq.heappush(q, (cost+1, nx, ny))
    
    print(ans)



if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())

    INF = int(1e7)
    a = np.array([list(map(lambda x: 0 if x=="#" else INF, list(input().strip()))) for i in range(H)])

    for i in range(H-1):
        a[i+1] = np.minimum(a[i] + 1, a[i+1])
    for i in range(H-1, 0, -1):
        a[i-1] = np.minimum(a[i] + 1, a[i-1])
    
    for i in range(W-1):
        a[:, i+1] = np.minimum(a[:, i] + 1, a[:, i+1])
    for i in range(W-1, 0, -1):
        a[:, i-1] = np.minimum(a[:, i] + 1, a[:, i-1])

    print(np.max(a))

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

INF = 10 ** 20
n = int(input())
edges = [list(map(int, input().split())) for _ in range(n)]
dist = [[INF] * n for _ in range(n)]

edgeList = []
for i in range(n):
    for j in range(i, n):
        edgeList.append((edges[i][j], i, j))
edgeList.sort()

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], edges[i][k] + edges[k][j])
ans = 0
for c, i, j in edgeList:
    minCost = min([dist[i][k] + dist[k][j] for k in range(n) if (k != i and k != j)] + [INF])
    if c > minCost:
        print(-1)
        break
    if c < minCost:
        ans += c
else:
    print(ans)

### FIXED CODE ###

INF = 10 ** 20
n = int(input())
edges = [list(map(int, input().split())) for _ in range(n)]
dist = [[INF] * n for _ in range(n)]

edgeList = []
for i in range(n):
    for j in range(i, n):
        edgeList.append((edges[i][j], i, j))
edgeList.sort()

for k in range(n):
    edgesk = edges[k]
    for i in range(n):
        disti = dist[i]
        edgesik = edges[i][k]
        for j in range(n):
            if disti[j] > edgesik + edgesk[j]:
                disti[j] = edgesik + edgesk[j]

ans = 0
for c, i, j in edgeList:
    minCost = INF
    for k in range(n):
        if k in (i, j):continue
        if minCost > dist[i][k] + dist[k][j]:
            minCost = dist[i][k] + dist[k][j]
    if c > minCost:
        print(-1)
        break
    if c < minCost:
        ans += c
else:
    print(ans)
### BUGGY CODE ###

from math import ceil
class sqrt_tree:
    def __init__(self,dat,f):
        self.dat = dat
        self.sq = int(len(dat) ** 0.5)
        self.baqet = {}
        for fi in f:
            self.baqet[fi] = [fi(dat[i * self.sq:(i + 1) * self.sq]) for i in range(self.sq)]
    
    #query
    def q(self,f,l,r):
        r += 1
        if ceil(l / self.sq) >= r // self.sq:
            return f(self.dat[l:r])
        ret = f(self.baqet[f][ceil(l / self.sq):r // self.sq])
        if l % self.sq:
            ret = f(ret,f(self.dat[l:l + self.sq]))
        if r % self.sq:
            ret = f(ret,f(self.dat[r - r % self.sq:r]))
        return ret

import sys
f = sys.stdin

_, d = map(int, f.readline().split())

b = sorted([tuple(map(int,line.split()))[::-1] for line in f])

x = sqrt_tree([bi[2] for bi in b],[min,max])
y = sqrt_tree([bi[1] for bi in b],[min,max])

max_size = i = j = 0
while j < len(b) - 1:
    for k in range(j,-1,-1):
        if b[k][0] + d < b[j][0]:
            break
        i = k
    for k in range(i,len(b)):
        if b[i][0] + d < b[k][0]:
            break
        j = k

    max_size = max(max_size,(x.q(max,i,j) - x.q(min,i,j)) * (y.q(max,i,j) - y.q(min,i,j)))
    j+=1
    
print(max_size)

### FIXED CODE ###

import math
def segmentTree(dat, f, sentinel):
        pad = 2 ** math.ceil(math.log(len(dat),2))
        dat = [0] * pad + dat + [sentinel] * (pad - len(dat))
        for i in range(pad - 1, 0, -1):
            dat[i] = f(dat[i * 2],dat[i * 2 + 1])
        return dat

def get_lr(b,d):
    l = r = 0
    while r < len(b):
        while b[l] + d < b[r]:
            l += 1
        for r in range(r,len(b)):
            if b[l] + d < b[r]:
                r -= 1
                break
        r += 1
        yield l,r
        l += 1
    
import sys
f = sys.stdin

_, d = map(int, f.readline().split())

xyb = []
for line in f:
    xyb.append(tuple(map(int, line.split())))
from operator import itemgetter
xyb.sort(key=itemgetter(2))

x = [xybi[0] for xybi in xyb]
y = [xybi[1] for xybi in xyb]
b = [xybi[2] for xybi in xyb]

xmax = segmentTree(x,max,sentinel = 0)
xmin = segmentTree(x,min,sentinel = 2000000)
ymax = segmentTree(y,max,sentinel = 0)
ymin = segmentTree(y,min,sentinel = 2000000)


pad = len(xmax) // 2
max_size = 0
def create_index(l,r):
    index = []
    ia = index.append
    while l < r:
        if r & 1:
            r -= 1
            ia(r)
        if l & 1:
            ia(l)
            l += 1
        l >>= 1
        r >>= 1
    return index

for l,r in get_lr(b,d):
    l += pad 
    r += pad
    index = create_index(l,r)

    now_xmax = max(xmax[i] for i in index)
    now_ymax = max(ymax[i] for i in index)
    if max_size < now_xmax * now_ymax:
        max_size = max(max_size,((now_xmax - min(xmin[i] for i in index)) * (now_ymax - min(ymin[i] for i in index))))
print(max_size)
### BUGGY CODE ###

n = int(input())
a = [0] * (n+1)
for i in range(n):
    a[i+1] = tuple(map(int, input().split()))
todo = [0] * (n+1)
days = 0
while True:
    update = []
    for i in range(1, n+1):
        if todo[i] < n - 1 and i not in update:
            p = a[i][todo[i]]
            if a[p][todo[p]] == i:
                update.append(i)
    for j in update:
        todo[j] += 1
    days += 1
    #print(todo)
    if update == []:
        days = -1
        break
    elif todo[1:] == [n - 1] * n:
        break
print(days)

### FIXED CODE ###

n = int(input())
a = []
for _ in range(n+1):
    a.append([-1])
for i in range(n):
    inp = list(map(int, input().split()))
    for j in range(n-2, -1, -1):
        a[i+1].append(inp[j])
matched = [i for i in range(1, n+1)]
finish = 0
days = 0
while True:
    used = set()
    while matched != []:
        i = matched.pop()
        p = a[i][-1]
        if p != -1 and a[p][-1] == i and (i not in used) and (p not in used) :
            a[i].pop()
            a[p].pop()
            used.add(i)
            used.add(p)
            if a[i][-1] == -1:
                finish += 1
            if a[p][-1] == -1:
                finish += 1
    days += 1
    matched = list(used)
    if len(used) == 0:
        days = -1
        break
    elif finish == n:
        break
print(days)
### BUGGY CODE ###

import numpy as np
Num = np.zeros((3,3),dtype=int)
for T in range(0,3):
    Num[T,:] = np.array([int(X) for X in input().split()])
               
Flag = False
MIN  = [min(Num[X,:]) for X in range(0,3)]+[min(Num[:,X]) for X in range(0,3)]
for R1 in range(MIN[0]+1):
    for R2 in range(MIN[1]+1):
        for R3 in range(MIN[2]+1):
            for C1 in range(MIN[3]+1):
                for C2 in range(MIN[4]+1):
                    for C3 in range(MIN[5]+1):
                        Sum = np.array([[R1+C1,R1+C2,R1+C3],[R2+C1,R2+C2,R2+C3],[R3+C1,R3+C2,R3+C3]])
                        if np.all(Sum==Num):
                            Flag = True
if Flag:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import numpy as np
Num = np.zeros((3,3),dtype=int)
Flag = False
for T in range(0,3):
    Num[T,:] = np.array([int(X) for X in input().split()])
for T in range(0,3):
    Num[:,T] -= Num[0,T]
for A2 in range(min(Num[1,:]),max(Num[1,:])+1):
    AB2 = np.array([A2+Num[0,0],A2+Num[0,1],A2+Num[0,2]])
    if np.all(AB2==Num[1,:]):
        for A3 in range(min(Num[2,:]),max(Num[2,:])+1):
            AB3 = np.array([A3+Num[0,0],A3+Num[0,1],A3+Num[0,2]])
            if np.all(AB3==Num[2,:]):
                Flag = True
                break
    if Flag:
        break     
if Flag:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

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

h = list(map(int,input().split()))

turn = 0

h.sort(reverse = True)

while len(h)>0 and k>0:
    del h[0]
    k -= 1
    
turn += sum(h)

print(turn)

### FIXED CODE ###

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

h = list(map(int,input().split()))

if k>=n:
    print(0)
    
else:
    h.sort()
    print(sum(h[:n-k]))
### BUGGY CODE ###

N,K,Q=map(int,input().split())
Q_list=[input() for i in range(Q)]  
#print(Q_list)
list_count=[]
for i in range(1,N+1):
  a=Q_list.count(str(i))
  list_count.append(a)
#print(list_count)
def ans(j):
  y=list_count[j]
  d=K-Q+y
  if 0>=d:
    return "No"
  else:
    return "Yes"
for j in range(0,N):
  print(ans(j))
#for j in range(0,N):
#  y=list_count[j]
#  d=K-Q+y
#  if 0>=d:
#    print("No")
#  else:
#    print("Yes")


### FIXED CODE ###

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

A=[K]*N
for i in range(Q):
  a=int(input())
  A[a-1] +=1
for i in range(len(A)):
  
  if A[i]-Q<=0:
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

y=int(input())
b=[[i,j,k]  for i in range(1,y+1) for j in range(1,y+1) for k in range(1,y+1) ]
c=[]
for l in range(y**3):
    import math
    a = b[l]
    ans1 = math.gcd(a[0], a[1])
    ans2 =math.gcd(ans1,a[2])
    c.append(ans2)
print(sum(c))   

### FIXED CODE ###

import math
y=int(input())
cnt=0
for i in range (1,y+1):
    for k in range(1,y+1):
        for j in range(1,y+1):
            a = [i,j,k]#リスト
            ans = a[0]
            for x in range(len(a)):
                ans = math.gcd(ans, a[x])
            cnt+=ans
print(cnt)
### BUGGY CODE ###

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

dp = [[0]*s for _ in range(n+1)]

fac_inv2 = pow(2,MOD-2,MOD)

for i in range(n):
    if a[i]<=s:
        dp[i+1][a[i]-1] = dp[i][a[i]-1] + 1
    for j in range(min(a[i]-1,s)):
        dp[i+1][j] = dp[i][j]
    for j in range(s-a[i]):
        dp[i+1][j+a[i]] = dp[i][j+a[i]] + (dp[i][j] * fac_inv2) %MOD
        dp[i+1][j+a[i]] %= MOD

ans = dp[-1][-1]

ans *= pow(2,n-1,MOD)
ans %= MOD
print(ans)

### FIXED CODE ###

import numpy as np

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


fac_inv2 = pow(2,MOD-2,MOD)

dp = np.zeros(s,"int64")

for i in range(n):
    
    newdp = dp.copy()
    if a[i]<s:
        newdp[a[i]:] += dp[:s-a[i]] * fac_inv2 % MOD
    if a[i]<=s:
        newdp[a[i]-1] += 1
    dp = newdp % MOD

ans = dp[-1]
ans *= pow(2,n-1,MOD)
ans %= MOD
print(ans)
### BUGGY CODE ###

def main():
    import numpy as np
    n, k = map(int, input().split())
    H = list(map(int, input().split()))
    s = np.array(sorted(set(H+[0])), dtype=np.int64)
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    a = max(s)-s
    dp = np.full((1, l), 10**13, dtype=np.int64)
    dp[0, 0] = 0

    if k > 0:
        for i in range(n):
            h = H[i]
            dh = d[h]
            dp2 = np.zeros((min(i+2, k+1), l), dtype=np.int64)
            if i < k:
                s_plus_a = a+dp[:]
                min_s = dp[:]
            else:
                s_plus_a = a+dp[:-1]
                min_s = dp[:-1]
            for j in range(l-2, -1, -1):
                min_s[:, j] = np.minimum(min_s[:, j+1], min_s[:, j])
            for j in range(1, l):
                s_plus_a[:, j] = np.minimum(s_plus_a[:, j-1], s_plus_a[:, j])
            dp2[1:, :] = np.minimum(min_s, s_plus_a - a)
            dp2[0, :] = 10**13
            if i < k:
                for j in range(l):
                    dp2[:-1, dh] = np.minimum(dp2[:-1, dh],
                                              dp[:, j]+max(h-s[j], 0))
            else:
                for j in range(l):
                    dp2[:, dh] = np.minimum(
                        dp2[:, dh], dp[:, j]+max(h-s[j], 0))
            dp = dp2
    else:
        for h in H:
            dh = d[h]
            dp2 = np.full((1, l), 10**13, dtype=np.int64)
            for j in range(l):
                dp2[:, dh] = np.minimum(dp2[:, dh], dp[:, j]+max(h-s[j], 0))
            dp = dp2
    print(np.min(dp))


main()

### FIXED CODE ###

def main():
    n, K = map(int, input().split())
    H = list(map(int, input().split()))
    s = sorted(set(H+[0]))
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    m = max(s)
    a = [m-i for i in s]
    dp = [[10**13]*l for _ in range(K+1)]
    dp[0][0] = 0
    for h in H:
        dh = d[h]
        dp2 = [[0]*l for _ in range(K+1)]
        dp2[0] = [10**13]*l
        t = [[0]*l for _ in range(K)]
        for i in range(K):
            for j in range(l):
                t[i][j] = dp[i][j]+a[j]
        min_s = [[10**13]*l for i in range(K+1)]

        for i in range(K):
            for j in range(l-2, -1, -1):
                min_s[i][j] = min(dp[i][j+1], min_s[i][j])
            for j in range(1, l):
                t[i][j] = min(t[i][j-1], t[i][j])
            for j in range(l):
                t[i][j] = t[i][j]-a[j]

        for i in range(K):
            for j in range(l):
                dp2[i+1][j] = min(min_s[i][j], t[i][j])

        for i in range(K+1):
            temp = 10**13
            for j in range(l):
                temp = min(temp, dp[i][j]+max(h-s[j], 0))
            dp2[i][dh] = min(dp2[i][dh], temp)
        dp = dp2
    print(min([min(i) for i in dp]))


main()
### BUGGY CODE ###

from operator import itemgetter
from itertools import permutations

N = int(input())
XL = [tuple(map(int, input().split())) for _ in range(N)]

XL = sorted(XL, key=itemgetter(0))

for i in range(N):
    for remove in permutations(XL, i):
        remained = [i for i in XL if i not in remove]
        edge = []
        for remain in remained:
            x, l = remain
            edge.append(x-l)
            edge.append(x+l)
        if edge == sorted(edge):
            print(len(remained))
            exit()

### FIXED CODE ###

n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
le = [[p[0]-p[1], p[0]+p[1]] for p in xl]
le.sort(key = lambda x : x[1])

ans = 0
right = -(10 ** 9) - 1
for i in range(n):
    if right <= le[i][0]:
        ans += 1
        right = le[i][1]

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

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

for i in range(M//N,0,-1):
    if M%i==0:
        print(i)
        break



### FIXED CODE ###

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

base=M//N
li=[]


for i in range(1,int(pow(M,1/2))+1):
    if i<=base and M%i==0:
        li.append(i)
    if M%i==0 and M//i<=base:
        li.append(M//i)

print(max(li))
### BUGGY CODE ###

import numpy as np

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


b=[]
for i in range(1,n):
  b.append(a[i]+a[0])

c=[i for i in range(n)]

b=np.array(b)
c=np.array(c)
c=c[1:]

ans=0
ans+=np.sum(b==c)
for i in range(1,n):
  b+=a[i]-a[i-1]
#  b=b[1:]

  c-=1
#  c=c[1:]

  ans+=np.sum(b==c)

print(ans)

### FIXED CODE ###

from collections import Counter

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

q1=[]
q2=[]

for i in range(n):
  q1.append(i+a[i])
  q2.append(i-a[i])

c1=Counter(q1)
c2=Counter(q2)

ans=0
for i in c1.keys():
  num1=c1[i]
  num2=c2[i]
  ans+=num1*num2

print(ans)