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

import sys
input = sys.stdin.readline
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

N,M = map(int,input().split())
PQC = [[int(x) for x in input().split()] for _ in range(M)]

V = set((x,0) for x in range(1,N+1))
V |= set((p,c) for p,q,c in PQC)
V |= set((q,c) for p,q,c in PQC)
V = list(V)
v_to_i = {v:i for i,v in enumerate(V)}

# グラフを作成
rows = []
cols = []
wt = []
for i,(p,c) in enumerate(V):
    if c != 0:
        j = v_to_i[(p,0)]
        rows.append(i)
        cols.append(j)
        wt.append(1)
for p,q,c in PQC:
    i = v_to_i[(p,c)]
    j = v_to_i[(q,c)]
    rows.append(i)
    cols.append(j)
    wt.append(0)

graph = csr_matrix((wt, (rows, cols)), (len(V), len(V)))

start = v_to_i[(1,0)]
goal = v_to_i[(N,0)]

dist = dijkstra(graph, directed = False, indices = start)[goal]

answer = -1 if dist == float('inf') else int((dist + 1)//2)
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

L = 32
mask = (1 << L) - 1
N,M = map(int,input().split())
graph = defaultdict(list)
for _ in range(M):
    p,q,c = map(int,input().split())
    p <<= L
    q <<= L
    graph[p].append(p+c)
    graph[p+c].append(p)
    graph[q].append(q+c)
    graph[q+c].append(q)
    graph[p+c].append(q+c)
    graph[q+c].append(p+c)

INF = 10 ** 9
dist = defaultdict(lambda: INF)

start = 1 << L
goal = N << L

q = [start] # 0 が会社に属していない状態
dist[start] = 0
d = 0
while q:
    qq = []
    while q:
        x = q.pop()
        if x & mask == 0:
            for y in graph[x]:
                if dist[y] <= d + 1:
                    continue
                dist[y] = d + 1
                qq.append(y)
        else:
            for y in graph[x]:
                if dist[y] <= d:
                    continue
                dist[y] = d
                q.append(y)
    d += 1
    q = qq

answer = dist[goal]
if answer == INF:
    answer = -1
print(answer)
### BUGGY CODE ###

import sys
n=int(input())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))

day=0
last_i=0
jyunban=[i for i in range(n)]
jyunban.insert(0,last_i)
match=[0 for i in range(n)]
while True:
  day+=1
  check=[True for i in range(n)]
  for i in jyunban:
    if match[i]>=n-1:
      check[i]=False
    if check[i]==False:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[i] and check[vs] and a[i][match[i]]-1==vs and a[vs][match[vs]]-1==i:
        match[i]+=1
        match[vs]+=1
        check[i]=False
        check[vs]=False
      
    if i==n-1:
      if not False in check:
        print(-1)
        sys.exit()
  if min(match)==n-1 and min(match)==max(match):
    break
        
print(day)
      
    


### FIXED CODE ###

import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
 
N = I()
a = [IL()[::-1] for i in range(N)]
 
used = [-1]*N
updatelist = [i for i in range(N)]
total = N*(N-1)//2
cnt = 0
days = 0
ul = []
while updatelist:
  ul = []
  for i in updatelist:
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        ul.append(i)
        ul.append(numIND)
        cnt += 1
  else:
    updatelist = ul[:]
    if len(ul) != 0:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)
### BUGGY CODE ###

def Binary_Search_Small_Count(A,x,sort=True,equal=False):
    """2分探索によって,x未満の要素の個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"未満"がx"以下"になる
    """
    if sort:
        A.sort()
        
    N=len(A)
    if A[-1]<x:
        return N
    elif x<A[0] or (not equal and x==A[0]):
        return 0

    L,R=0,N
    while R-L>1:
        C=L+(R-L)//2
        if x<A[C] or (not equal and x==A[C]):
            R=C
        else:
            L=C
    return R
#=======================================
N=int(input())
L=list(map(int,input().split()))
L.sort()

K=0
for i in range(N):
    for j in range(i+1,N):
        a,b=L[i],L[j]
        X=Binary_Search_Small_Count(L,a+b,False,False)
        Y=Binary_Search_Small_Count(L,b,True,False)
        K+=X-Y

        if b<=a<a+b:
            K-=1
        if b<=b<a+b:
            K-=1
print(K)


### FIXED CODE ###

def Binary_Search_Small_Count(A,x,sort=True,equal=False):
    """2分探索によって,x未満の要素の個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"未満"がx"以下"になる
    """
    if sort:
        A.sort()
        
    N=len(A)
    if A[-1]<x:
        return N
    elif x<A[0] or (not equal and x==A[0]):
        return 0

    L,R=0,N
    while R-L>1:
        C=L+(R-L)//2
        if x<A[C] or (not equal and x==A[C]):
            R=C
        else:
            L=C
    return R
#=======================================
N=int(input())
L=list(map(lambda x:int(x),input().split()))
inf=float("inf")

T={}
for i in range(N):
    x=L[i]
    if x in T:
        T[x]+=1
    else:
        T[x]=0
        
    L[i]=(x,T[L[i]])
L.sort()

D=0
for i in range(N):
    (b,y)=L[i]
    for j in range(i+1,N):
        (c,z)=L[j]

        X=Binary_Search_Small_Count(L,(b,y),False,False)
        Y=Binary_Search_Small_Count(L,(c-b,inf),False,True)

        D+=max(0,X-Y)
print(D)
### BUGGY CODE ###

N = int(input())
X = input()
M = {X[0:3]:1}
result = {}

for i in range(3,N):
    i = X[i]
    keys = M.keys()
    for j in tuple(keys):
        if (j, i) in result:
            continue
        M[j[0]+j[1]+i] = 1
        M[j[0]+j[2]+i] = 1
        M[j[1]+j[2]+i] = 1
        result[(j,i)] = True

print (len(M))

### FIXED CODE ###

N = int(input())
X = input()
#X = "196341362415710923461093419237419237417234162348162390471092374190237410982374901"*300
#N = len(X)
M = { }
A = set()
A.add(X[0]+X[1])
for i in range(2, N) :
    i = X[i]
    for j in tuple(A):
        M[j + i] = 1
        A.add(j[0]+i)
        A.add(j[1]+i)

    if len(M) == 1000:
        break
print(len(M))
### BUGGY CODE ###

from heapq import  heappush, heappop

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i for i in input()] for _ in range(H)]

dist = [[float('inf')] * W for _ in range(H)]
dist[x1 - 1][y1 - 1] = 0
q = [(0, x1 - 1, y1 - 1)]
while q :
  ccost, cx, cy = heappop(q)
  if ccost > dist[cx][cy] :
    continue
  for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)) :
    for i in range(1, K + 1) :
      nx, ny = dx * i + cx, dy * i + cy
      ncost = ccost + 1
      if not (0 <= nx < H and 0 <= ny < W and c[nx][ny] != '@' and ncost <= dist[nx][ny]) :
        break
      heappush(q, (ncost, nx, ny))
      dist[nx][ny] = ncost

if dist[x2 - 1][y2 - 1] == float('inf') :
  print(-1)
else :
  print(dist[x2 - 1][y2 - 1])

### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i == '.' for i in input()] for _ in range(H)]

x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
INF = 1 << 60
dist = [INF] * (H * W * 2)

def pos(x, y, m) :
  return (x * W + y) * 2 + m
dist[pos(x1, y1, 0)] = dist[pos(x1, y1, 1)] = 0

q = [(0, pos(x1, y1, 0)), (0, pos(x1, y1, 1))]
while q :
  ccost, cpos = heappop(q)
  if ccost > dist[cpos] : continue
  cx = cpos // 2 // W
  cy = cpos // 2 % W
  cmode = cpos % 2
  dir = [
    [(-1, 0), (1, 0)],
    [(0, -1), (0, 1)]
  ]
  for dx, dy in dir[cmode] :
    nx, ny = cx + dx, cy + dy
    ncost = ccost + 1
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] and ncost < dist[pos(nx, ny, cmode)] :
      heappush(q, (ncost, pos(nx, ny, cmode)))
      dist[pos(nx, ny, cmode)] = ncost
      
  ncost = (ccost + K - 1) // K * K
  if ncost < dist[pos(cx, cy, cmode ^ 1)] :
    dist[pos(cx, cy, cmode ^ 1)] = ncost
    heappush(q, (ncost, pos(cx, cy, cmode ^ 1)))

ans = min(dist[pos(x2, y2, 0)], dist[pos(x2, y2, 1)])
if ans == INF :
  print(-1)
else :
  print((ans + K - 1) // K)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
B = A
A = np.array(A)
B = np.array(B)
emp = np.zeros(N)
Amax_ind = np.argmax(A)
emp[Amax_ind:] = max(A)
A[Amax_ind:] = 0
while 0 in emp:
    subAmax_ind = np.argmax(A)
    emp[subAmax_ind:Amax_ind] = max(A)
    A[subAmax_ind:Amax_ind] = 0
    Amax_ind = subAmax_ind
print(int(sum(emp-B)))
    

### FIXED CODE ###

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

ans = 0
cur_max = 0

for x in a:
    if cur_max > x:
        ans += cur_max - x
    cur_max = max(cur_max, x)

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

A,B=map(int,input().split())
H=[0]*1000

i=1
while i<=999:
    H[i]=i+H[i-1]
    i+=1

ans=0
while True:
    if (A+ans in H)and(B+ans==H[H.index(A+ans)+1] in H):
        break
    else:
        ans+=1
    
print(ans)

### FIXED CODE ###

A,B=map(int,input().split())
H=[0]*1000

i=1
while i<=999:
    H[i]=i+H[i-1]
    i+=1

ans=0
while True:
    if (A+ans in H)and(B+ans==H[H.index(A+ans)+1] in H):
        break
    else:
        ans+=1
    
print(ans)
### BUGGY CODE ###

K = int(input())

if K < 10:
    print(K)
else:
    count = 0
    num = 1
    runrun = list(range(1, 10))
    while count != K:
        s = str(num)
        judge = 0
        for i in range(1, len(s)):
            if abs(int(s[i - 1]) - int(s[i])) <= 1:
                judge += 1
            else:
                break
        
        if judge == len(s) - 1:
            runrun.append(num)
            count += 1
            

        num += 1
    print(num - 1)

### FIXED CODE ###

K = int(input())

queue = list(range(1, 10))

if K < 10:
    print(K)
else:
    i = 0
    while K > len(queue):
        if queue[i] % 10 != 0:
            l = 10 * queue[i] + queue[i] % 10 - 1
            queue.append(l)
        
        l = 10 * queue[i] + queue[i] % 10
        queue.append(l)
        
        if queue[i] % 10 != 9:
            l = 10 * queue[i] + queue[i] % 10 + 1
            queue.append(l)
        
        i += 1

    print(queue[K - 1])
### BUGGY CODE ###


K = int(input())

import math
from functools import reduce

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

dammy = []
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            dammy.append(gcd(a, b, c))

print(sum(dammy))


### FIXED CODE ###

import fractions
K = int(input())

gcd = [[0]*K for i in range(K)]
L = [0]*K

for a in range(1,K+1):
    for b in range(1,K+1):
        A = fractions.gcd(a,b)
        gcd[a-1][b-1] = A
        L[A-1] +=1

sum=0
for c in range(1,K+1):
    for i in range(1,K+1):
        B = gcd[c-1][i-1]
        sum +=  B * L[i-1]

print(sum)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# 1つ目の入力
num = int(input())

# スペース区切りの整数の入力
num_list = list(map(int,input().split()))

def judge(num_list, num):
    if num == 1:
        return('Yes')
    for i in range(0,len(num_list)-1):
        for j in range(i+1,len(num_list)):
          if num_list[i] -1 <= num_list[j]:
            if i+1 == num-1:
                return('Yes')
          else:
            return('No')


print(judge(num_list, num))

### FIXED CODE ###

# -*- coding: utf-8 -*-

# 1つ目の入力
num = int(input())

# スペース区切りの整数の入力
num_list = list(map(int,input().split()))

def judge(num_list, num):
    if num == 1:
        return('Yes')

    decrease = False
    for i in range(0,len(num_list)):
        if i + 1 == num:  # 終わりなので、何もしない
            return('Yes')  # 最後までOKだったので、Yesをリターン

        if num_list[i] == num_list[i+1]:
            pass
        elif num_list[i] < num_list[i+1]:
            decrease = False
        elif num_list[i] - 1 <= num_list[i+1]:
            if decrease:
                return('No')
            else:
                decrease = True
        else:
            return('No')
        '''
        for j in range(i+1,len(num_list)):
          if num_list[i] -1 <= num_list[j]:
            if i+1 == num-1:
                return('Yes')
          else:
            return('No')
        '''


print(judge(num_list, num))
### BUGGY CODE ###

import numpy as np
s = input()
t = input()

dp = np.zeros((len(s) + 1, len(t) + 1), dtype=int)

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

answer = ''
i, j = len(s), len(t)
now = dp[i, j]
while i > 0 and j > 0:
    if dp[i-1, j] == now:
        i -= 1
        continue
    if dp[i, j-1] == now:
        j -= 1
        continue
    answer += s[i-1]
    i -= 1
    j -= 1
    now -= 1

print(answer[::-1])


### FIXED CODE ###

s = input()
t = input()

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

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

answer = ''
i, j = len(s), len(t)
now = dp[i][j]
while i > 0 and j > 0:
    if dp[i-1][j] == now:
        i -= 1
        continue
    if dp[i][j-1] == now:
        j -= 1
        continue
    answer += s[i-1]
    i -= 1
    j -= 1
    now -= 1

print(answer[::-1])
### BUGGY CODE ###

#入力
N = int(input())
Alist = list(map(int,input().split()))
Alist.sort()
Q = int(input())
Blist = []
Clist = []
for i in range(Q):
  B, C = map(int,input().split())
  Blist.append(B)
  Clist.append(C)

for j in range(Q):
  num = Alist.count(Blist[j])
  if num == 0:
    pass
  else:
    firstindex = Alist.index(Blist[j])
    for l in range(num):
      Alist[firstindex+l] = Clist[j]
  print(sum(Alist))
  Alist.sort()

### FIXED CODE ###

import collections
#入力
N = int(input())
n = 100001
Alist = list(map(int,input().split()))
Q = int(input())
Blist = []
Clist = []
for i in range(Q):
  B, C = map(int,input().split())
  Blist.append(B)
  Clist.append(C)

Adic = dict(collections.Counter(Alist))
numlist = [0]*n

for j in range(n):
  if j in Adic:
    numlist[j] = Adic[j]
sum = sum(Alist)
for k in range(Q):
  sum += (Clist[k]-Blist[k])*numlist[Blist[k]]
  numlist[Clist[k]] += numlist[Blist[k]] 
  numlist[Blist[k]] = 0

  print(sum)
### BUGGY CODE ###

a,b,k=map(int, input().split())
for i in range(a,b+1):
  if i<=a+k-1 or b-k+1<=i:
    print(i,end=" ")

### FIXED CODE ###

a,b,k=map(int,input().split())
ans=[]
for i in range(a,min(a+k,b+1)):
    ans.append(i)
for j in range(b,max(b-k,a-1),-1):
    if j not in ans:
        ans.append(j)
ans.sort()
for k in range(len(ans)):
  print(ans[k])
### BUGGY CODE ###

from itertools import permutations as per
s=list(input())
t=list(input())
n=len(t)
s=list(per(s))
t=list(per(t))

def f(x):
    m=1
    while x>0:
        m*=x
        x=x-1
    return m
x=s[0]
y=t[f(n)-1]
l=s+t
l=sorted(l)
if l.index(x)<l.index(y):
    print("Yes")
else:
    print("No")


### FIXED CODE ###


s=list(input())
t=list(input())
s=sorted(s)
t=sorted(t)
x=s[0]
for i in range(len(s)-1):
    x=x+s[i+1]
y=t[-1]
for i in range(len(t)-1):
    y=y+t[-i-2]




l=[]
l.append(x)
l.append(y)
l=sorted(l)

if l.index(x)<l.index(y):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import numpy as np
L, R = map(int, input().split())

minimum=2019
for i in range(L, R):
    for j in range(i+1, R+1):
        tmp = (i*j)%2019
        if minimum>tmp:
            minimum = tmp
    if minimum==0:
        continue
print(minimum)

### FIXED CODE ###

L, R = map(int, input().split())

minimum=2019
z=0
for i in range(L, R+1):
    for j in range(i+1, R+1):
        tmp = (i*j)%2019
        if minimum>tmp:
            minimum = tmp
        if minimum==0:
            z=1
            break
    if z==1:
        break
    
print(minimum)
### BUGGY CODE ###

#SumofThreeIntegers
k, s = map(int, input().split())
cnt = 0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x + y + z == s :
        cnt += 1
print(cnt)

### FIXED CODE ###

#SumofThreeIntegers
k, s = map(int, input().split())
cnt = 0
for x in range(k+1):
  for y in range(k+1):
    a = s - (x + y)
    if 0 <= a <= k :
      cnt += 1
print(cnt)
### BUGGY CODE ###

#!/usr/bin/python3

from fractions import Fraction

M = 1000000007

def normalize(v):
    if v > 0:
        return v
    else:
        return - 1 / v

n = int(input())

vs = {}
zc = 0
azc = 0
bzc = 0

for i in range(n):
    (a, b) = map(int, input().split())
    if a == 0 and b == 0:
        zc += 1
        continue

    if a == 0:
        azc += 1
        continue

    if b == 0:
        bzc += 1
        continue

    v = Fraction(a, b)
    if v in vs:
        vs[v] += 1
    else:
        vs[v] = 1

wp = set()
for v in vs:
    if - 1 / v in vs:
        wp.add(normalize(v))

#print(zc, azc, bzc, vs, wp)
        
c = 1
if azc == 0 or bzc == 0:
    c = c * pow(2, azc + bzc, M) % M
else:
    c = c * (pow(2, azc, M) - 1 + pow(2, bzc, M) - 1 + 1) % M

r = n - azc - bzc
for p in wp:
    invp = -1 / p
    c = c * (pow(2, vs[p], M) - 1 + pow(2, vs[invp], M) - 1 + 1) % M
    r -= vs[p] + vs[invp]

r -= zc
c = c * pow(2, r, M) % M
c = (c + zc) % M
c = (c - 1) % M

print(c)





    


### FIXED CODE ###

#!/usr/bin/python3

import math

M = 1000000007

def normalize(v):
    (a, b) = v
    if a * b > 0:
        return (a, b)
    else:
        if a > 0:
            return (-b, a)
        else:
            return (b, -a)
    
def inv(v):
    (a, b) = v
    if a > 0:
        return (-b, a)
    else:
        return (b, -a)
    
    
n = int(input())

vs = {}
zc = 0
azc = 0
bzc = 0

for i in range(n):
    (a, b) = map(int, input().split())
    if b < 0:
        a = -a
        b = -b

    g = math.gcd(a, b)
        
    if a == 0 and b == 0:
        zc += 1
        continue

    if a == 0:
        azc += 1
        continue

    if b == 0:
        bzc += 1
        continue

    (a, b) = (a // g, b // g)
    if (a, b) in vs:
        vs[(a, b)] += 1
    else:
        vs[(a, b)] = 1

wp = set()
for v in vs:
    if inv(v) in vs:
        wp.add(normalize(v))

#print(zc, azc, bzc, vs, wp)
        
c = 1
if azc == 0 or bzc == 0:
    c = c * pow(2, azc + bzc, M) % M
else:
    c = c * (pow(2, azc, M) - 1 + pow(2, bzc, M) - 1 + 1) % M

r = n - azc - bzc
for p in wp:
    invp = inv(p)
    c = c * (pow(2, vs[p], M) - 1 + pow(2, vs[invp], M) - 1 + 1) % M
    r -= vs[p] + vs[invp]

r -= zc
c = c * pow(2, r, M) % M
c = (c + zc) % M
c = (c - 1) % M

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

import itertools
N,K = map(int,input().split())
count = 0
list_abc = list(itertools.product(range(1,N+1),repeat = 3))
for i in list_abc:
  if (i[0] + i[1])%K==0 and (i[1] + i[2])%K==0 and (i[0] + i[2])%K==0:
    count = count +1
print(count)

### FIXED CODE ###

N,K = map(int,input().split())
ans1 = 0
ans2 = 0
for i in range(1,N+1):
    if i%K == 0:
        ans1 += 1
if K%2 == 0:
    for i in range(1,N+1):
        if i%K == K//2:
            ans2 += 1
print(ans1**3 + ans2**3)
### BUGGY CODE ###

import math
import copy
H,N=map(int,input().split())

#inf=float('inf')
dp=[0]+[1e8]*H

for i in range(N):
    A,B=map(int,input().split())
    if A>=H:
        dp[-1]=min(B,dp[-1])
    else:
        for j in range(A,H+1):
            dp[j]=min(dp[j-A]+B,dp[j])

            if j > H-A:
                dp[-1]=min(dp[-1],dp[j]+B)


print(dp[-1])


### FIXED CODE ###

import math

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

    inf=float('inf')
    dp=[0]+[inf]*H

    for i in range(N):
        A,B=map(int,input().split())
        if A>=H:
            #dp[-1]=min(B,dp[-1])
            if B < dp[-1]:
                dp[-1]=B
        else:
            for j in range(A,H+1):
                #dp[j]=min(dp[j-A]+B,dp[j])
                if dp[j-A]+B<dp[j]:
                    dp[j]=dp[j-A]+B

                if j > H-A:
                    #dp[-1]=min(dp[-1],dp[j]+B)
                    if dp[j]+B < dp[-1]:
                        dp[-1]=dp[j]+B

    print(dp[-1])

main()
### BUGGY CODE ###

class Node:
    def __init__(self,data):
        self.data=data
        self.left=None
        self.right=None
class BST:
    def __init__(self,number_list):
        self.root=None
        for node in number_list:
            self.insert(node)
    def insert(self,data):
        n=self.root
        if n is None:
            self.root=Node(data)
            return
        else:
            while True:#これ抜けてた。やばい。
                entry=n.data
                if data<entry:
                    if n.left is None:
                        n.left=Node(data)
                        return
                    n=n.left
                elif data>entry:
                    if n.right is None:
                        n.right=Node(data)
                        return
                    n=n.right
                else:
                    n.data=data
                    return
    def search(self,target):
        n = self.root
        if n is None:
            return None
        else:#深さ優先探索
            lst = []
            lst.append(n)
            while len(lst) > 0:
                node = lst.pop()
                if node.data == target:
                    return True
                if node.right is not None:
                    lst.append(node.right)
                if node.left is not None:
                    lst.append(node.left)
            return False
        
import math
N=int(input())
a=list(map(int,input().split()))
t_max=int(math.log2(max(a)*2)+1)
ans=0
for t in range(t_max,0,-1):
    i=0
    while i<len(a):
    #forだとout of rangeしてしまうので。
        x,y=0,0
        bst=BST(a)#二分木も更新しないと。
        if bst.search(2**t-a[i]):
            if a[i]!=2**t-a[i]:
                #同じだったらNG
                ans+=1
                x+=a[i]
                y+=2**t-a[i]
                #IDを共有すると、インデックスがずれる。
                a.remove(x)
                a.remove(y)
        else:
            i+=1 #ペアが見つからなかったときだけ進めばいい。
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
c = Counter(a)

ans = 0
for i in a:
    if c[i] == 0:
        continue
    c[i] -= 1
    k = 1<<i.bit_length()
    j = k-i
    if j in c and c[j] > 0:
        ans += 1
        c[j] -= 1
print(ans)
### BUGGY CODE ###

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

Asp = []
for a in As:
    Asp.append(a // 2)


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


import functools

l = functools.reduce(lcm, Asp)

fg = False
for a in Asp:
    if (l // a) % 2 == 0:
        fg = True
        break

if fg:
    print("0")
else:
    print(M // l - M // (l * 2))

### FIXED CODE ###

N, M = map(int, input().split())
As = list(map(lambda a: int(a) >> 1, input().split()))

from fractions import gcd

l = As[0]
for a in As:
    l = l * a // gcd(l, a)
    if l > M:
        break

if l <= M:
    i = 2
    while l & (i - 1) == 0:
        i <<= 1
    i = (i >> 1) - 1

    fg = False
    if i > 0:
        for a in As:
            if a & i > 0:
                fg = True
                break

    if fg:
        print(0)
    else:
        print(M // l - M // (l * 2))
else:
    print(0)
### BUGGY CODE ###

n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]

dp=[[0]*(W+1) for i in range(n+1)]
for i in range(n-1,-1,-1):
  for j in range(W+1):
    if j<items[i][0]:
      dp[i][j]=dp[i+1][j]
    else:
      dp[i][j]=max(dp[i+1][j],dp[i+1][j-items[i][0]]+items[i][1])

print(dp[0][W])
    

### FIXED CODE ###

import sys
input=sys.stdin.readline

n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
import numpy as np

dp=np.zeros([n+1,W+1],dtype=np.int64)
for i in range(n):
  w=items[i][0]
  v=items[i][1]
  dp[i+1][:w]=dp[i][:w]
  dp[i+1][w:]=np.maximum(dp[i][w:],dp[i][:-w]+v)
print(dp[-1][-1])