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

N, K = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(K)]

dp = [0] * (N + 1)
dp_sums = [0] * (N + 1)
dp[1] = dp_sums[1] = 1

for i in range(1,N+1):
    for s in S: 
        if i >= s[1] + 1:
            dp[i] += dp_sums[i - s[0]] - dp_sums[i - s[1] - 1] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i > s[0] and i < s[1] + 1:
            dp[i] += dp_sums[i - s[0]] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i <= s[0]:
            dp_sums[i] = dp_sums[i-1] + dp[i]
        while dp[i] >= 998244353:
            dp[i] -= 998244353
while dp[N] >= 998244353:
    dp[N] -= 998244353 
print(dp[N])

### FIXED CODE ###

N, K = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(K)]

dp = [0] * (N + 1)
dp_sums = [0] * (N + 1)
dp[1] = dp_sums[1] = 1

for i in range(2,N+1):
    for l, r in S: 
        if i >= r + 1:
            dp[i] += dp_sums[i - l] - dp_sums[i - r - 1] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i > l and i < r + 1:
            dp[i] += dp_sums[i - l] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i <= l:
            dp_sums[i] = dp_sums[i-1] + dp[i]
    dp[i] %= 998244353
    dp_sums[i] %= 998244353
print(dp[N])
### BUGGY CODE ###

import sys
#大きすぎるとダメ
sys.setrecursionlimit(2530)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)




### FIXED CODE ###

#一個だけRE、わからねえ
#解答見る
import sys
sys.setrecursionlimit(1005)
h,w=map(int,input().split())

def go_next(I,J,n):
    n+=1
    global dp,w,h
    if n>1000:
        return
    if 0<=I<h-1:
        if x[I+1][J]=="." and dp[I+1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J,n)
    if 0<I<=h-1:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J,n)
    if 0<=J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1,n)
    if 0<J<=w-1:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1,n)

x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l1=[a[0]]
l2=[]
def al(num):
    l1.append(num)
for i in range(n):
    num1=a[l1[-1]-1]
    str=num1 in l1
    if str==True:
        for j in range(len(l1)):
            if l1[j]==num1:
                break
        l2=l1[j:]
        l1=l1[:j]
        break
    else:
        al(num1)
num1=len(l1)
num2=len(l2)
if k<=num1:
    print(l1[k-1])
else:
    num3=(k-num1)%num2
    print(l2[num3-1])


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l1=set([a[0]])
num1=a[0]
num2=1
l2=[]
def al(num):
    l1.add(num)
def n2(num5):
    return num5 in l1
for i in range(n):
    num1=a[num1-1]
    al(num1)
    if num2==len(l1):
        break
    else:
        num2=len(l1)
l1=list(l1)
num=l1.index(num1)
l2=l1[num:]
l1=l1[:num]
num1=len(l1)
num2=len(l2)
if k<=num1:
    print(l1[k-1])
else:
    num3=(k-num1)%num2
    print(l2[num3-1])
### BUGGY CODE ###

while True:
    m,n=map(int,raw_input().split())
    if m==n==0:break
    L=range(1,m+1)
    j=0
    for i in range(1,n+1):
        c=raw_input()
        if i%15==0:
            if c!="FizzBuzz":
                L[j]=0
        elif i%5==0:
            if c!="Buzz":
		L[j]=0
	elif i%3==0:
            if c!="Fizz":
		L[j]=0
        elif c<>str(i):
            L[j]=0
        j+=1
        while L[j%m]==0:
            j=(j+1)%m
        j%=m
    print " ".join([str(i) for i in L if i!=0])

### FIXED CODE ###

def Judge(i):
    if i%15==0: return "FizzBuzz"
    if i%5==0:  return "Buzz"
    if i%3==0:  return "Fizz"
    return str(i)

while True:
    m,n=map(int,raw_input().split())
    if m==n==0:break
    L=range(1,m+1)
    j=0
    for i in range(1,n+1):
        c=raw_input()
	if len(L)>1:
            if Judge(i)!=c:
                del L[j]
                j%=len(L)
            else:
                j=(j+1)%len(L)
    print " ".join(map(str,L))
### BUGGY CODE ###

n = int(input())
can = []
xyh = []
for _ in range(n):
  xyh.append(list(map(int,input().split())))
time = 0
while xyh[time][2] == 0:
  time += 1
x,y,h = xyh[time]
for i in range(101):
  for j in range(101):
    can.append([i, j, h + abs(x-i) + abs(y-j)])
step = 0
while len(can) != 1:
  x,y,h = xyh[(time + step) % n]
  if h != 0:
    cnt = 0
    while cnt < len(can):
      now = can[cnt]
      if now[2] != h + abs(x-now[0]) + abs(y-now[1]):
        del can[cnt]
      else:
        cnt += 1
  else:
    cnt = 0
    while cnt < len(can):
      now = can[cnt]
      if now[2]  < abs(x-now[0]) + abs(y-now[1]):
        del can[cnt]
      else:
        cnt += 1
  step += 1
print(' '.join(list(map(str,can[0]))))

### FIXED CODE ###

n = int(input())
can = []
xyh = []
for _ in range(n):
  xyh.append(list(map(int,input().split())))
time = 0
while xyh[time][2] == 0:
  time += 1
x,y,h = xyh[time]
for i in range(101):
  for j in range(101):
    can.append([i, j, h + abs(x-i) + abs(y-j)])
step = 0
while len(can) != 1:
  x,y,h = xyh[(time + step) % n]
  if h != 0:
    cnt = 0
    while cnt < len(can):
      now = can[cnt]
      if now[2] != h + abs(x-now[0]) + abs(y-now[1]):
        del can[cnt]
      else:
        cnt += 1
  else:
    cnt = 0
    while cnt < len(can):
      now = can[cnt]
      if now[2] > abs(x-now[0]) + abs(y-now[1]):
        del can[cnt]
      else:
        cnt += 1
  step += 1
print(' '.join(list(map(str,can[0]))))
### BUGGY CODE ###

MOD = 10**9+7
l = input()
n = len(l)
dp = [    [0,0] for _ in range(n + 1)]
dp[0][0]  = 1
#dp[桁数][条件を満たすことが確定しているフラグ]
# 00 10 01

for i in range(1,n +1):
    # (dp[i][flag]のflag,dp[i-1][flag]のflag,i桁目の数字) で繊維は2**3の8通り
    dp[i][1] += dp[i - 1][1] * 3 # i桁目が (0,1) flag が 1 1
    #flag 0→1はない

    if l[i-1] == "1":
        dp[i][0] += dp[i -1][0] * 2 #1,0  or 0,1のときに相変わらず未定
        dp[i][1] += dp[i -1][0] # 0,0のときだけ確定させられる e.g. 101 10 のときに次に0が来れば確定 なので0,0
    else:
        dp[i][0] +=dp[i-1][0] # 0,0 の場合のみ
        # dp[i][1] への遷移は無し
ans = dp[-1][0] + dp[-1][1]
print(ans % MOD)


### FIXED CODE ###

MOD = 10**9+7
l = input()
n = len(l)
dp = [    [0,0] for _ in range(n + 1)]
dp[0][0]  = 1
#dp[桁数][条件を満たすことが確定しているフラグ]
# 00 10 01

for i in range(1,n +1):
    # (dp[i][flag]のflag,dp[i-1][flag]のflag,i桁目の数字) で繊維は2**3の8通り
    dp[i][1] += dp[i - 1][1] * 3 # i桁目が (0,1) flag が 1 1
    #flag 0→1はない

    if l[i-1] == "1":
        dp[i][0] += dp[i -1][0] * 2 #1,0  or 0,1のときに相変わらず未定
        dp[i][1] += dp[i -1][0] # 0,0のときだけ確定させられる e.g. 101 10 のときに次に0が来れば確定 なので0,0
    else:
        dp[i][0] +=dp[i-1][0] # 0,0 の場合のみ
        # dp[i][1] への遷移は無し
    dp[i][0] %= MOD
    dp[i][1] %= MOD
ans = dp[-1][0] + dp[-1][1]
print(ans % MOD)
### BUGGY CODE ###

n, k = map(int, input().split())
h = []
ans = 1000000001
for i in range(n):
    h.append(int(input()))
h.sort()
for j in range(n-(k-1)):
    x = []
    for l in range(j,j+k):
        x.append(h[l])
        if ans == 0:
            break
        elif len(x) == k:
            y = x[-1]-x[0]
            if ans == 0:
                break
            elif ans > y:
                ans = y
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
h = []
ans = 1000000001
for i in range(n):
    h.append(int(input()))
h.sort()
for j in range(n-(k-1)):
    if ans == 0:
        break
    elif ans > h[j+k-1]-h[j]:
        ans = h[j+k-1]-h[j]
print(ans)
### BUGGY CODE ###

def shichigo(s):
    if '3' not in s:
        return False
    if '5' not in s:
        return False
    if '7' not in s:
        return False
    x = s.replace('3','').replace('5','').replace('7','')
    if x=='':
        return True
    return False


n = input()

# k = 桁数-1
k = len(n)-1

# k桁までの753数
ans = 0
for i in range(1,k+1):
    ans += 3**i - 3*2**i + 3

# nの桁の753数/3
a = 3**k - 2**(k+1) + 1

f = int(n[0])

if f<3:
    print(ans)
    exit()
elif f==3:
    for i in range(3*10**k,int(n)+1):
        if shichigo(str(i)):
            ans += 1
elif f<5:
    ans += a
elif f ==5:
    ans += a
    for i in range(5*10**k,int(n)+1):
        if shichigo(str(i)):
            ans += 1
elif f<7:
    ans += 2*a
elif f==7:
    ans += 2*a
    for i in range(7*10**k,int(n)+1):
        if shichigo(str(i)):
            ans += 1
else:
    ans += 3*a

print(ans)

### FIXED CODE ###

def shichigo(s):
    if '3' not in s:
        return False
    if '5' not in s:
        return False
    if '7' not in s:
        return False
    x = s.replace('3','').replace('5','').replace('7','')
    if x=='':
        return True
    return False

n = input()

l = [[] for i in range(len(n))]
l[0] = ['3','5','7']
for i in range(1,len(l)):
    for j in range(len(l[i-1])):
        l[i].append('3'+l[i-1][j])
        l[i].append('5'+l[i-1][j])
        l[i].append('7'+l[i-1][j])

ans = 0
for i in range(len(l)):
    for j in range(len(l[i])):
        if int(n) >= int(l[i][j]):
            if shichigo(l[i][j]):
                ans += 1

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

n, k = tuple(map(int, input().split()))
arr = [0 for i in range(n)]
sums = 0
for i in range(n):
    inp = int(input())
    arr[i] = inp

arr.sort()

sa = 1000000000
for i in range(n-k+1):
    newsa = max(arr[i:i+k]) - min(arr[i:i+k])
    if newsa < sa:
        sa = newsa

print(sa)


### FIXED CODE ###

n, k = tuple(map(int, input().split()))
arr = [0 for i in range(n)]
sums = 0
for i in range(n):
    inp = int(input())
    arr[i] = inp

arr.sort()

sa = 1000000000
for i in range(n-k+1):
    newsa = arr[i+k-1] - arr[i]
    if newsa < sa:
        sa = newsa

print(sa)
### BUGGY CODE ###

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

for i in range(len(p_list)):
  p_list[i] += 1
  p_list[i] /= 2

ans = 0
for i in range(N-K+1):
  if ans < sum(p_list[i:i+K]):
    ans = sum(p_list[i:i+K])

print(ans)

### FIXED CODE ###

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

for i in range(len(p_list)):
  p_list[i] += 1
  p_list[i] /= 2

sum_p = sum(p_list[0:K])
ans = sum_p
for i in range(1, N-K+1):
  sum_p = sum_p - p_list[i-1] + p_list[i+K-1]
  if ans < sum_p:
    ans = sum_p

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

N, W = map(int, input().split())
ws = [0]*N
vs = [0]*N

for i in range(N):
  w, v = map(int, input().split())
  ws[i] = w
  vs[i] = v
V = sum(vs)+1
  

dp = [[float('inf')]*(V) for _ in range(N+1)]
# dp[i][j]: i個の品物を使ってjの価値を実現する最小のw
dp[0][0] = 0
temp = 0

for i in range(N):
  w = ws[i]
  v = vs[i]
  for j in range(i, -1, -1):
    for k in range(temp+1):
      dp[j+1][k+v] = min(dp[j][k]+w, dp[j+1][k+v])
  temp += v

ans = 0
for i in range(N+1):
  for j in range(V):
    if dp[i][j] <= W:
      ans = max(ans, j)
print(ans)

### FIXED CODE ###

N, W = map(int, input().split())
ws = [0]*N
vs = [0]*N

for i in range(N):
  w, v = map(int, input().split())
  ws[i] = w
  vs[i] = v

V = N*(10**3)+1
dp = [[float('inf')]*V for _ in range(N+1)]
# dp[i][j]: i個の品物までを見てjの価値を実現する最小のw
dp[0][0] = 0
temp = 0

for i in range(N):
  w = ws[i]
  v = vs[i]
  for k in range(V):
    if k-v>=0:
      dp[i+1][k] = min(dp[i][k-v]+w, dp[i+1][k])
    dp[i+1][k] = min(dp[i][k], dp[i+1][k])

for j in range(V-1, -1, -1):
  if dp[N][j] <= W:
    print(j)
    exit()
### BUGGY CODE ###

N = int(input())
L = [input() for i in range(N)]
c = [L.count(j) for j in L]
C = max(c)
l = [L[k] for k in range(N) if c[k] == C]
m = list(set(l))
m.sort()
[print(n) for n in m]

### FIXED CODE ###

import collections
N = int(input())
l = [input() for i in range(N)]
L = collections.Counter(l)
a = L.most_common()
M = a[0][1]
A = [j[0] for j in a if j[1] == M]
[print(k) for k in sorted(A)]
### BUGGY CODE ###

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

S = [0 for i in range(H+4)]
S[0] = "#"*(W+4)
S[1] = "#"*(W+4)
S[H+2] = "#"*(W+4)
S[H+3] = "#"*(W+4)
for i in range(2, H+2):
  S[i] = "##" + input() + "##"
  
B = [ [-1 for i in range(W+4)] for i in range(H+4)]

def search(i,j,c):
  global B
  B[i][j] = c
  L = [(-1,0), (1, 0), (0, -1), (0, 1)]
  for X in L:
    if S[i+X[0]][j+X[1]] == '.' and B[i+X[0]][j+X[1]] < 0:
        search(i+X[0],j+X[1],c)
        
#<01>[2--H+1]<H+2,3>#
c = 0
for i in range(2,H+2):
  for j in range(2,W+2):
    if S[i][j] == '.' and B[i][j] < 0:
      search(i, j, c)
      c += 1

Cc = B[Ch+1][Cw+1]
Dc = B[Dh+1][Dw+1]
dic = {i:set() for i in range(c)}

for i in range(2, H+2):
  for j in range(2, W+2):
    if B[i][j] >= 0:
      for x in range(-2, 3):
        for y in range(-2, 3):
          if S[i+x][j+y] == '.' and B[i][j] != B[i+x][j+y]:
            dic[B[i][j]].add(B[i+x][j+y])

ans = [-1 for i in range(c)]
ans[Cc] = 0
not_check = [1 for i in range(c)]
not_check[Cc] = 0
next_check = {Cc}
#
t = 0
while len( next_check ):
  t += 1
  tmp = set()
  for i in next_check:
    for j in dic[i]:
      if not_check[j]:
        not_check[j] = 0
        ans[j] = t
        tmp.add( j )
  next_check = {i for i in tmp}
#
print(ans[Dc])

### FIXED CODE ###

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

S = [0 for i in range(H+4)]
S[0] = "#"*(W+4)
S[1] = "#"*(W+4)
S[H+2] = "#"*(W+4)
S[H+3] = "#"*(W+4)
for i in range(2, H+2):
  S[i] = "##" + input() + "##"
  
B = [ [-1 for i in range(W+4)] for i in range(H+4)]

def search(i,j,c):
  global B
  B[i][j] = c
  L = [(-1,0), (1, 0), (0, -1), (0, 1)]
  for X in L:
    if S[i+X[0]][j+X[1]] == '.' and B[i+X[0]][j+X[1]] < 0:
        search(i+X[0],j+X[1],c)
        
#<01>[2--H+1]<H+2,3>#
c = 0
for i in range(2,H+2):
  for j in range(2,W+2):
    if S[i][j] == '.' and B[i][j] < 0:
      search(i, j, c)
      c += 1

Cc = B[Ch+1][Cw+1]
Dc = B[Dh+1][Dw+1]
dic = {i:set() for i in range(c)}

for i in range(2, H+2):
  for j in range(2, W+2):
    if B[i][j] >= 0:
      for x in range(-2, 3):
        for y in range(-2, 3):
          if S[i+x][j+y] == '.' and B[i][j] != B[i+x][j+y]:
            dic[B[i][j]].add(B[i+x][j+y])

ans = [-1 for i in range(c)]
ans[Cc] = 0
not_check = [1 for i in range(c)]
not_check[Cc] = 0
next_check = {Cc}
#
t = 0
while len( next_check ):
  t += 1
  tmp = set()
  for i in next_check:
    for j in dic[i]:
      if not_check[j]:
        not_check[j] = 0
        ans[j] = t
        tmp.add( j )
  next_check = {i for i in tmp}
#
print(ans[Dc])
### BUGGY CODE ###

import sys
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
count =1 #ボタンを押した回数用 
s=0 #スタートするボタン　これを操作ボタンにしていく
while True:
    if a[s]==2:
        print(count)
        sys.exit()
    elif count>1 and s==0:
        print(-1)
        sys.exit()
    else:
        count+=1
        s=a[s]-1



### FIXED CODE ###

import sys
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
count =1 #ボタンを押した回数用 
s=0 #スタートするボタン　これを操作ボタンにしていく
while True:
    if a[s]==2:
        print(count)
        sys.exit()
    elif count>n:
        print(-1)
        sys.exit()
    else:
        count+=1
        s=a[s]-1
### BUGGY CODE ###

N,K=(int(x) for x in input().split())
x=N
if K!=1:
     while True:
        x = abs(x-K)
        y=abs(x-K)
        if y>x:
            break
     print(x)
else:
    print(0)

### FIXED CODE ###

N,K=(int(x) for x in input().split())
x=N%K
if K!=1:
     while True:
        x = abs(x-K)
        y = abs(x-K)
        if y>x:
            break
     print(x)
else:
    print(0)
### BUGGY CODE ###

import sys
n, q = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

ans = [0]*n
for i in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x

def DFS(node, p_node=-1):
    for c_node in graph[node]:
        if c_node==p_node:
            continue
        ans[c_node] += ans[node]
        DFS(c_node, node)

sys.setrecursionlimit(2*n)
DFS(0)
print(*ans)

### FIXED CODE ###

from collections import deque
n, q = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

ans = [0]*n
for _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x

stack = deque([0])
seen = [False]*n
while len(stack) > 0:
    parent = stack.pop()
    seen[parent] = True
    for child in graph[parent]:
        if seen[child]:
            continue
        ans[child] += ans[parent]
        stack.append(child)

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

from collections import deque
import copy

n = int(input())
p = list(map(int, input().split()))
for i in range(len(p)):
    p[i] -= 1

to_outsides = [[0 for _ in range(n)] for _ in range(n)]
not_exist = [["■" for _ in range(n)] for _ in range(n)]


for i in range(n):
    for j in range(n):
        to_outside = [i,n-1-i,j,n-1-j]
        to_outsides[i][j] = min(to_outside)

directions = [[-1,0],[1,0],[0,-1],[0,1]]

all_loss = 0
answer = 0
for i, person in enumerate(p):
    exited = [person//n, person%n]
    answer += to_outsides[exited[0]][exited[1]]
    not_exist[exited[0]][exited[1]] = "□"
    seen = []
    seen.append([exited[0],exited[1]])
    todo = deque([exited])
    renews = []
    while len(todo)>0:
        now = todo.pop()
        renews.append(now)
        for direction in directions:
            try:
                checking = [now[0]+direction[0],now[1]+direction[1]]
                to_outsides[checking[0]][checking[1]]
            except:
                continue
            if [checking[0],checking[1]] not in seen and\
            ((not_exist[checking[0]][checking[1]] == "□" and  to_outsides[checking[0]][checking[1]]==to_outsides[now[0]][now[1]])or\
            to_outsides[checking[0]][checking[1]]>to_outsides[now[0]][now[1]]):
                todo.append([checking[0],checking[1]])
                seen.append([checking[0],checking[1]])
    
    for renew in renews:
        if to_outsides[renew[0]][renew[1]] != 0:
            to_outsides[renew[0]][renew[1]]-=1
print(answer)


### FIXED CODE ###

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

dp = [[min(i, N - i - 1, j, N - j - 1) for j in range(N)] for i in range(N)]

presence = [[1 for j in range(N)] for i in range(N)]

ans = 0
for i in range(len(P)):
    P[i] -= 1
    x, y = divmod(P[i], N)
    ans += dp[x][y]
    presence[x][y] = 0

    Q = [(x, y)]
    #%%
    while Q:
        x, y = Q.pop()
        new_value = dp[x][y] + presence[x][y]
        if 1 <= x and dp[x - 1][y] > new_value:
            dp[x - 1][y] = new_value
            Q.append((x - 1, y))
        if x < N - 1 and dp[x + 1][y] > new_value:
            dp[x + 1][y] = new_value
            Q.append((x + 1, y))
        if 1 <= y and dp[x][y - 1] > new_value:
            dp[x][y - 1] = new_value
            Q.append((x, y - 1))
        if y < N - 1 and dp[x][y + 1] > new_value:
            dp[x][y + 1] = new_value
            Q.append((x, y + 1))

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

n,m = map(int,input().split())
list = [[int(i) for i in input().split()] for i in range(n)]
temp = [0]
ans = 0
a = 0
list = sorted(list)
for i in range(1,1+m):
  for j in range(a,len(list)):
    if list[j][0] == i:
      temp.append(list[j][1])
    else:
      a = j
      break
  ans += max(temp)
  l = int(len(temp) -1)
  if l >= 1:
    temp = sorted(temp)
    temp = temp[:l]
print(ans)

### FIXED CODE ###

import heapq as hp
import sys
def input():
    return sys.stdin.readline()

n,m = map(int,input().split())
list = [[int(i) for i in input().split()] for i in range(n)]
temp = [0]
ans = 0
a = 0
j = 0
list = sorted(list)

for i in range(1,1+m):
  for j in range(a,len(list)):
    if list[j][0] == i:
      hp.heappush(temp,-list[j][1])
    else:
      a = j
      break
  if len(temp) > 0:
    ans -= hp.heappop(temp)
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
answer = 0
if k == 1:
  answer = 0
elif k >= n:
  gap = k-n
  if gap > n:
    answer = n
  else:
    answer = gap
else:
  while n > k:
    n = n - k
  if k >= n:
    gap = k-n
    if gap > n:
      answer = n
    else:
      answer = gap
print(answer)

### FIXED CODE ###

n,k = map(int,input().split())
answer = 0
if k >= n:
  gap = k-n
  if gap > n:
    answer = n
  else:
    answer = gap
else:
  sho = n // k
  if n % k == 0:
    dec = sho - 1
  else:
    dec = sho
  n = n - k*dec
  if k >= n:
    gap = k-n
    if gap > n:
      answer = n
    else:
      answer = gap
print(answer)
### BUGGY CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

n=input()
lst=[int(n[i]) for i in range(len(n))]
# for i in range(len(n)):
#     lst.append(int(n[i]))
# n=int(n)

keta=len(lst)
ans=0
lst.reverse()

dp=[[float('inf')]*2 for i in range(keta+1)]
dp[0]=[0,1]
# print(dp)
for i in range(keta):
    dp[i+1][0]=min(dp[i][0]+lst[i],dp[i][1]+lst[i]+1)
    dp[i+1][1]=min(dp[i][0]+(10-lst[i]),dp[i][1]+(10-lst[i]-1))
# print(dp)
print(min(dp[-1][0],dp[-1][1]+1))

### FIXED CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

n=input()
lst=[]
for i in range(len(n)):
    lst.append(int(n[i]))
# n=int(n)

keta=len(lst)
ans=0
lst.reverse()
# print(lst)
# dp=[[float('inf')]*2 for i in range(keta+1)]
dp=[]
for i in range(keta+1):
    dp.append([float('inf')]*2)
dp[0]=[0,1]
# print(dp)
for i in range(keta):
    dp[i+1][0]=min(dp[i][0]+lst[i],dp[i][1]+lst[i]+1)
    dp[i+1][1]=min(dp[i][0]+(10-lst[i]),dp[i][1]+(10-lst[i]-1))
# print(dp)
print(min(dp[-1][0],dp[-1][1]+1))
### BUGGY CODE ###

import fractions
from functools import reduce
N,*a=map(int,open(0).read().split())
_max=0
for i in a:
    b=a[:]
    b.remove(i)
    _max=max(_max,reduce(fractions.gcd,b))
print(_max)

### FIXED CODE ###

import fractions
#from functools import reduce
N,*a=map(int,open(0).read().split())
L=[]
L_base=a[0]
b=a[:]
b.reverse()
R=[]
R_base=b[0]
for i in range(N-1):
    L_base=fractions.gcd(L_base,a[i])
    L.append(L_base)
    R_base=fractions.gcd(R_base,b[i])
    R.append(R_base)
LR=[R[-1]]
for i in range(N-2):
    LR.append(fractions.gcd(L[i],R[-2-i]))
LR.append(L[-1])
print(max(LR))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations

def inpl(): return tuple(map(int, input().split()))

N = int(input())
A = inpl()

print(min([abs(sum(A[:i])-sum(A[i:])) for i in range(1, N)]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

N = int(input())
A = inpl()
s = sum(A)

x, y = A[0], sum(A[1:])
res = abs(x-y)

for a in A[1:-1]:
    x += a
    y -= a
    if abs(x-y) < res:
        res = abs(x-y)
print(res)
### BUGGY CODE ###

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

q = int(input())
a = input()
t=list(map(int,a.split()))

i = 0
for it in t:
    if it in s:
        i = i+1
print(i)

### FIXED CODE ###

def gost(lis,ky,r,l):
    
    lens=l-r+1
    
    if lens <= 5:
        if ky in lis[r:l+1]:
            return True
        else:
            return False
    
    if ky <= lis[r+(lens//2)-1]:
        return gost(lis,ky,r,r+(lens//2)-1)
    else:
        return gost(lis,ky,r+(lens//2),l)
    

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

q = int(input())
a = input()
t=list(map(int,a.split()))


i = 0
for it in t:
    if gost(s,it,0,n-1):
        i = i+1
print(i)