Harryxun/stf_run huggingface dataset:
#import numpy as np
import sys
input = sys.stdin.readline


def main():
    h, n = map(int, input().split())
    A = []
    B = []
    for _ in range(n):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
        
        m = 2 * 10**4 + 10
        dp = [10**5] * (h+1)
        for a, b in zip(A, B):
            dp[a] = b
            for i in range(h):
                for a, b in zip(A, B):
                    if i + a < m and dp[i] > 0:
                        j = min(i+a, h)
                        if dp[j] > 0:
                            dp[j] = min(dp[j], dp[i] + b)
                        else:
                            dp[j] = dp[i] + b
    k = h
    # print(dp[:20])
    # while (flag):
    #     if dp[k] > 0:
    #         ans = dp[k]
    #         flag = 0
    #     k += 1
    # d = np.array(dp[k:])
    # print(np.min(d[d.nonzero()]))
    print(dp[h])
    
    
main()


### FIXED CODE ###

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


def main():
    h, n = map(int, input().split())
    # A = []
    # B = []
    # for _ in range(n):
    #     A.append(a)
    #     B.append(b)
        
    m = 2 * 10**4 + 10
    dp = [float("inf")] * (h+1)
    dp[0] = 0
    # for a, b in zip(A, B):
    #     dp[a] = b
    for _ in range(n):
        a, b = map(int, input().split())
        for i in range(h):
            # for a, b in zip(A, B):
            if i + a < m :
                j = min(i+a, h)
                if dp[j] > 0:
                    dp[j] = min(dp[j], dp[i] + b)
                else:
                    dp[j] = dp[i] + b
    k = h
    # print(dp[:20])
    # while (flag):
    #     if dp[k] > 0:
    #         ans = dp[k]
    #         flag = 0
    #     k += 1
    # d = np.array(dp[k:])
    # print(np.min(d[d.nonzero()]))
    print(dp[h])
    
    
main()
def bin_tree( pri , li_pri , len_li ):
    #pri: どこに入れていいかわからない値段
    #li_pri: 値段のリスト(昇順)
    #len_li: リストの長さ
    lo = 0
    hi = len_li - 1
    while hi - lo > 1:
        mid = lo + (hi - lo) // 2
        guess = li_pri[mid]
        if guess >= pri:
            hi = mid
        else:
            lo = mid
    return lo

I = input().split()
N = int(I[0])
M = int(I[1])
# N: 品物の数
# M: 割引券の数
# A: 品物の値段行列
A = list(map(int , input().split()))
A.sort()

print(A)

while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2

    ans = bin_tree( pri , A , N - 1 ) + 1
    # ans: pri以上となる値段のうち最小のインデックス
    A[ans:ans] = [pri]

    print(A)
    

F_pri = 0
for i in range(N):
    F_pri += A[i]
print(F_pri)

### FIXED CODE ###

def bin_tree( pri , li_pri , len_li ):
    #pri: どこに入れていいかわからない値段
    #li_pri: 値段のリスト(昇順)
    #len_li: リストの長さ
    lo = 0
    hi = len_li - 1
    while hi - lo > 1:
        mid = lo + (hi - lo) // 2
        guess = li_pri[mid]
        if guess >= pri:
            hi = mid
        else:
            lo = mid
    return lo

I = input().split()
N = int(I[0])
M = int(I[1])
# N: 品物の数
# M: 割引券の数
# A: 品物の値段行列
A = list(map(int , input().split()))
A.sort()

while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2
    if len(A) == 0:
        ans = 0
    elif (pri < A[0] ):
        ans = 0
    else:
        ans = bin_tree( pri , A , N - 1 ) + 1
    # ans: pri以上となる値段のうち最小のインデックス
    A[ans:ans] = [pri]    

F_pri = 0
for i in range(N):
    F_pri += A[i]
print(F_pri)
from collections import Counter
N = int(input())
a = list(map(int, input().split()))
i_list = []
#return tuple list: Counter().most_common()                                                                          for i in a:
    i_list.append(i-1)
    i_list.append(i)
    i_list.append(i+1)
print(Counter(i_list).most_common()[0][1])

### FIXED CODE ###

from collections import Counter
N = int(input())
a = list(map(int, input().split()))
i_list = []
for i in a:
    i_list.append(i-1)
    i_list.append(i)
    i_list.append(i+1)
print(Counter(i_list).most_common()[0][1])
import math
if kotae_dic == {}: # 一つの桁に複数の値の時        
    print(-1)
else:
    kotae_dic_sorted = sorted(kotae_dic.items(),key=lambda x:int(x[0]))
    kotae_str = "".join( [i[1][0] for i in kotae_dic_sorted ] ) # 辞書の値を連結
    kotae_int =int(kotae_str)
    if kotae_int == 0 and 1< N: # "00"などはエラー、"0"はOK
        print(-1)
    elif kotae_int == 0 and N == 1:
        print("0")
    elif 10**(N-1) > kotae_int or kotae_int >= 10** N: # 桁があってない＝一番左の桁が”０”はエラー
        print(-1)
    else:
        print(kotae_int)

### FIXED CODE ###


from collections import defaultdict
N,M = (int(x) for x in input().split())
keta_num_str = [ (input().split()) for i in range(M) ]

#各桁をキー、数字を値の辞書にする
suuji = ""
num_str_dic = defaultdict(set)
kotae_dic ={ str(i):"0" for i in range(1,N +1) } #　各桁に初期値”０”を入力。一番右（１の位）は入力がなければ無し
if 1< N:
    kotae_dic["1"] = "1" # 2桁以上の時は左の桁は最低１
for i in keta_num_str:   
    num_str_dic[i[0]].add(i[1])


for i,v in num_str_dic.items():
    if 1 < len(v) : # 一つの桁に複数の値がある時はエラー
        kotae_dic ={}
        break
    
    else:
        kotae_dic[i] = list(v)[0]

# 表示
import math
if kotae_dic == {}: # 一つの桁に複数の値の時        
    print(-1)
else:
    kotae_dic_sorted = sorted(kotae_dic.items(),key=lambda x:int(x[0]))
    kotae_str = "".join( [i[1] for i in kotae_dic_sorted ] ) # 辞書の値を連結
    kotae_int =int(kotae_str)
    if kotae_int == 0 and 1< N: # "00"などはエラー、"0"はOK
        print(-1)
    elif kotae_int == 0 and N == 1:
        print("0")
    elif 10**(N-1) > kotae_int or kotae_int >= 10** N: # 桁があってない＝一番左の桁が”０”はエラー
        print(-1)
    elif kotae_dic["1"] == "0" and 1 < N: 
        kotae_dic["1"] ="1"
    elif 1000 <= kotae_int: # 答えが１０００以上はエラー
        print(-1)

    else:
        print(kotae_int)
A,B = input().split()
if B%A == 0:
  print(A + B)
else:
  print(A - B)

### FIXED CODE ###

A, B = (int(i) for i in input().split())  
if B%A == 0:
  print(A + B)
else:
  print(B - A)
H, W = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
res = [[-1 for _ in range(W)] for _ in range(H)]

x = 0
y = 0
for i in range(N):
    if x + A[i] <= W:
        for j in range(A[i]):
            res[y][x + j] = i + 1
            
        x = x + A[i]
            
    else:
        for j in range(x, W):
            res[y][j] = i + 1
            
        y = y + 1
        
        for j in range(A[i] - (W - x) + 1):
            res[y][j] = i + 1
            
        x = 0
        
for i in range(H):
    result = ''
    for j in range(W):
        result =  result + str(res[i][j])
        if j != W - 1:
            result += ' '
        
    print(result)
        

### FIXED CODE ###

H, W = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
res = [[-1 for _ in range(W)] for _ in range(H)]
tmp = []
for i in range(N):
    for j in range(A[i]):
        tmp.append(i + 1)
        
for i in range(H):
    result = ''
    for j in range(W):
        if i%2 == 0:
            result = result + str(tmp[W * i + j])
            if j != W - 1:
                result = result + ' '
        else:
            result =  str(tmp[W * i + j]) + result
            if j != W - 1:
                result = ' ' + result 
            
    print(result)
s=input()
 
if s[0] = 1:
    con + = 1
elif s[1] = 1:
    con + = 1
elif s[2] = 1:
    con + = 1
    print(1)

### FIXED CODE ###

s = input()
count = 0 
if s[0] == '1':
    count += 1
if s[1] == '1':
    count += 1
if s[2] == '1':
    count += 1
print(count)
n,m,k=map(int,input().split())
A=[0]+list(map(int,input().split()))
B=[0]+list(map(int,input().split()))

for a in A:
  A[a]+=A[a+1]
  
for b in B:
  B[b]+=B[b+1]

ans=0
op=m
for i in range(n+1):
  if A[i]>k:
    break
  while A[i]+B[op]>k:
    op-=1
   
  ans=max(ans,i+op)
  
print(ans)


### FIXED CODE ###

n,m,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

asum=[0]
bsum=[0]

for i in range(n):
  asum.append(asum[i]+A[i])
  
for j in range(m):
  bsum.append(bsum[j]+B[j])

ans=0
ko=m
for i in range(n+1):
  if asum[i]>k:
    break
  while asum[i]+bsum[ko]>k:
    ko-=1
  ans=max(ans,i+ko)
  
print(ans)
# 分割されていない文字列をどうやって分けるか
a = [*input()] #　これで一文字ずつになる
cnt = 0
if a[0] == "1":
        cnt +=1          
if a[1] == "1":
        cnt +=1          
if a[2] == "1":
        cnt +=1          

print(cnt)



### FIXED CODE ###

# 分割されていない文字列をどうやって分けるか
a = list(input())#　これで一文字ずつになる
cnt = 0
for i in a:
        if i == "1":
                cnt +=1          
print(cnt)
S = input()
plus = count('+')
minus = count('-')
print( plus - minus )

### FIXED CODE ###

S = input()
plus = S.count('+')
minus = S.count('-')
print( plus - minus )
A, B, C, D = map(int, input().split())

x = C / B
y = C % B
p = A / D
q = A % D

if (x > p):
  print("Yes")
elif (x < p):
  print("No")
else
  if (y == 0 and q <> 0):
    print("Yes")
  elif (y <> 0 and q == 0):
    print("No")
  else :
    print("Yes")


### FIXED CODE ###

A, B, C, D = map(int, input().split())
 
flg = True
t = False
while(flg):
  C -= B
  if (C <= 0):
    t = True
    break
  A -= D
  if (A <= 0) :
    t = False
    break

if (t):
  print("Yes")
else:
  print("No")
N = int(input())
A = list(map(int,input().split()))

number_list = [0]*100001
for a in A:
    number_list[a] += 1
    
flag1 = True
flag2 = True

for i in range(2,100001):
    count = 0
    for j in range(1,100001):
        if i*j > 100000:
            break
        tmp = i*j
        count += number_list[tmp]
    if count > 1:
        flag1 = False
    if count == N:
        flag2 = False
        
if flag2 == False and flag1 == False:
    print("not coprime")
elif flag2 == True and flag1 == False:
    print("setwise coprime")
else:
    print("pairwise coprime")

### FIXED CODE ###

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

number_list = [0]*1000010
for a in A:
    number_list[a] += 1
    
flag1 = True
flag2 = True

for i in range(2,1000001):
    count = 0
    for j in range(1,1000001):
        if i*j > 1000000:
            break
        tmp = i*j
        count += number_list[tmp]
    if count > 1:
        flag1 = False
    if count == N:
        flag2 = False
        
if flag2 == False and flag1 == False:
    print("not coprime")
elif flag2 == True and flag1 == False:
    print("setwise coprime")
else:
    print("pairwise coprime")
a = int(input())

while a > 10:
    a = a % 10

if a == 2 or a == 4 or a == 5 or a == 7 or a == 9
    print("hon")
elif a == 0 or a == 1 or a == 6 or a == 8:
    print("pon" )
else:
    print("bon" )


### FIXED CODE ###

a = int(input())

while a > 10:
    a = a % 10

if a == 2 or a == 4 or a == 5 or a == 7 or a == 9:
    print("hon")
elif a == 0 or a == 1 or a == 6 or a == 8:
    print("pon" )
else:
    print("bon" )
h,n=map(int,input().split())

ab=[]
dp=[10**9]*(10**4)

maxA=0
for _ in range(n):
    a,b=map(int,input().split())
    ab.append((a,b))
    dp[a]=b
    maxA=max(maxA,a)
#print(dp)
#dp[a]は、相手にaダメージを与えるときの、消耗する自分の最小HP
result=10**9
for i in range(1,h+maxA):
    #print(i,"##########")
    for k in range(1,i//2+2):
        dp[i]=min(dp[i],dp[k]+dp[i-k])
    if i>=h:
        result=min(result,dp[i])
    #print(dp)
print(result)



    
    



### FIXED CODE ###

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

ab=[]
dp=[10**9]*(10**5)

maxA=0
for _ in range(n):
    a,b=map(int,input().split())
    dp[a]=min(dp[a],b)
    maxA=max(maxA,a)
#print(dp)
#dp[a]は、相手にaダメージを与えるときの、消耗する自分の最小HP
result=10**9
for i in range(1,h+maxA):
    #print(i,"##########")
    for k in range(1,i//2+2):
        dp[i]=min(dp[i],dp[k]+dp[i-k])
    if i>=h:
        result=min(result,dp[i])
    #print(dp)
print(result)
s=input()
if s==ABA:
	print("Yes")
else:
	print()

### FIXED CODE ###

s=input()
a=s[0]
b=s[1]
c=s[2]
if a== b and b==c:
	print("No")
else:
	print("Yes")
n = input()
lst = map(int,raw_input().split())
for i in range(n):
	print lst[n-1+i],

### FIXED CODE ###

n = input()
lst = map(int,raw_input().split())
while n>0:
	n -= 1
	print lst[n],
a,b,c = input().split()
print(upper(a[0],b[0],c[0]))


### FIXED CODE ###

a,b,c = input().split()
b.upper()
print(a[0]+b[0]+c[0])
N = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))
h = []
for i in range(N):
    if i == 0:
        h.append(1)
    elif i == N - 1:
        h.append(1)
    else:
        if T[i] > T[i - 1]:
            h.append(1)
            if T[i] > A[i]:
                h[i] = 0
                break
        elif A[i] > A[i + 1]:
            h.append(1)
            if A[i] > T[i]:
                h[i] = 0
                break
        else:
            h.append(min([A[i], T[i]]) % 1000000007)

if max[T] != max[A]:
    h.append(0)
    
cnt = 1
for i in range(len(h)):
    cnt *= h[i]
                     
print(cnt % 1000000007)

### FIXED CODE ###

N = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))
h = []
for i in range(N):
    if i == 0:
        h.append(1)
    elif i == N - 1:
        h.append(1)
    else:
        if T[i] > T[i - 1]:
            h.append(1)
            if T[i] > A[i]:
                h[i] = 0
                break
        elif A[i] > A[i + 1]:
            h.append(1)
            if A[i] > T[i]:
                h[i] = 0
                break
        else:
            h.append(min([A[i], T[i]]))

if max(T) != max(A):
    h.append(0)
    
cnt = 1
for i in range(len(h)):
    cnt *= h[i]
    cnt %= 1000000007
                     
print(cnt % 1000000007)
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
 
DIV_NUM = 1000000000 + 7
 
INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])
 
A = [int(x) for x in input().split()]
AA = np.array(A , dtype='int64')
Q=np.array([0], dtype = 'int64')
if N==1:
    print(0)
    exit()
 
tree = [0] * (N+1)
 
# https://atcoder.jp/contests/chokudai_S001/submissions/6789704
def BIT_update(x):
    Q[0]=x
    while Q[0] <= N:
        tree[Q[0]] += 1
        Q[0] += Q[0]&(-Q[0])
def BIT_sum(x):
    s = 0
    Q[0]=x
    while Q[0] > 0:
        s += tree[Q[0]]
        Q[0] -= Q[0]&(-Q[0])
    return s
 
answer = N*(N-1)//2
for x in AA:
    answer -= BIT_sum(int(x))
    BIT_update(int(x))

#print(type(x),type(N))
#print(tree)


B = sorted(A)
 
q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r
 
# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)
 

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

DIV_NUM = 1000000000 + 7

INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])

A = [int(x) for x in input().split()]
AA = np.array(A)
if N==1:
    print(0)
    exit()

# https://kira000.hatenadiary.jp/entry/2019/02/23/053917
def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                cnt += 1
    return cnt

answer = bubble_sort(AA)

B = sorted(A)
q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r

# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)
A, B = [int(x) for x in input().split(" ")]

for k in range(0,10**9):
  if abs(A-k) == abs(B-k):
    print(k)
  else:
    print(IMPOSSIBLE)

### FIXED CODE ###

A, B = [int(x) for x in input().split(" ")]

if (A+B)%2 == 0:
  print(int((A+B)/2))
else:
  print("IMPOSSIBLE")
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math

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

if "1"*M in S:
  print(-1)
  exit()  

S = list(map(int,S))



### FIXED CODE ###

import sys
input = sys.stdin.readline

import math
import bisect

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

if "1"*M in S:
  print(-1)
  exit()  

S = [int(S[i]) for i in range(N+1)]

L = [(1<<i) -1 for i in range(1,M+1)]

max_n = [0]
mask = (1<<M) -1
b = 0
for i in range(N):
  b = ((b<<1) + (1- S[i])) & mask
  max_n.append(bisect.bisect_left(L,b)+1)

now = N
deme = []
while now != 0:
  x = max_n[now]
  now -= x
  deme.append(x)
print(*deme[::-1])
def calc(N, h, n):
    base = 4/N - 1/h - 1/n
    if base == 0:
        return False, 0
    ret = 1/base
    return ret == int(ret) and ret > 0, int(ret)

N = int(input())

def f(N):
    for h in range(1, 3501):
        for n in range(1, 3501):
            judge, ret = calc(N,h,n)
            if judge:
                return h, n, ret

print(*f(N))


### FIXED CODE ###

def calc(N, h, n):
    base = 4 * h * n - N * n - N * h
    if base <= 0:
        return False, -1
    ret = (N*h*n) / base
    return ret == int(ret) and 0 <= ret <= 3500, int(ret)

N = int(input())

def f(N):
    for h in range(1, 3501):
        for n in range(1, 3501):
            judge, ret = calc(N,h,n)
            if judge:
                return h, n, ret
    return -1, -1, -1

print(*f(N))
n = int(input())
a = map(int,input().split())

ans = 0
for i in range(n):
    for j in range(i):
       t = abs(a[j]-a[i])
       if ans < t:
           ans = t

print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(n):
    for j in range(i):
       t = abs(a[j]-a[i])
       if ans < t:
           ans = t

print(ans)
from itertools import product
import numpy as np


H, W, K = [int(n) for n in input().split()]
for _ in range(K):
  a = 1
print(1)

### FIXED CODE ###

from itertools import product
import numpy as np

H, W, K = [int(n) for n in input().split()]
arr = np.zeros((H, W))
count = 0

for h in range(H):
    row = input()
    arr[h, :] = np.array([0 if mark=='.' else 1 for mark in row])

for row_onehot, col_onehot in product(product(range(2), repeat=H), product(range(2), repeat=W)):
    row_indexes = np.argwhere(np.array(row_onehot)==1).flatten()
    col_indexes = np.argwhere(np.array(col_onehot)==1).flatten()
    arr_ = arr.copy()
    for row_idx in row_indexes:
        arr_[row_idx, :] = 0
    for col_idx in col_indexes:
        arr_[:, col_idx] = 0
    if arr_.sum() == K:
        count += 1

print(count)
from collection import Counter
S = list(input())

C = Counter(S)

ok = True
for s,x in list(C.items()):
  if x % 2 != 0:
    ok = False
    break

if ok:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

from collections import Counter
S = list(input())

C = Counter(S)

ok = True
for s,x in C.items():
  if x % 2 != 0:
    ok = False
    break

if ok:
  print("Yes")
else:
  print("No")
N = int(intput())
stocks = list(map(int, input().split()))
for i in range(N - 1):
  cnt = 0
  if stocks[i] < stocks[i + 1]:
    pass

### FIXED CODE ###

N = int(input())
stocks = list(map(int, input().split()))
curr = 1000
for i in range(N - 1):
  cnt = 0
  if stocks[i] < stocks[i + 1]:
    cnt = curr // stocks[i]
  curr += cnt * (stocks[i + 1] - stocks[i])
print(curr)
n,p = map(int,input().split())
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
a = primes(int(p**(1/n)))
res = 1
for j in range(len(a)):
 q = p
 if q%int(a[j]**n) == 0:
  c = 0
  while q%int(a[j]**n) == 0:
   q /= (a[j]**n)
   c += 1
  res *= int(a[j]**c)
print(res)

### FIXED CODE ###

n,p = map(int,input().split())
if n == 1:
  print(p)
  exit()
a = 1
for k in range(2,1000001):
  c = 0
  while p%k == 0:
    p = p//k
    c += 1
  a *= k**(c//n)
  if p == 1:
    break
print(a)
a, b, c, x, y = list(map(int, input().split()))
    res = a * x + b * y
    for i in range(1, max(x, y) + 1):
        res = min(res, a * max(x - i, 0) + b * max(y - i, 0) + 2 * c * i)
    print(res)

### FIXED CODE ###

a, b, c, x, y = list(map(int, input().split()))
res = a * x + b * y
for i in range(1, max(x, y) + 1):
    res = min(res, a * max(x - i, 0) + b * max(y - i, 0) + 2 * c * i)
print(res)
import collections

S = list(input())
T = list(input())

for i in range(len(S)):
	tmp = S[i:] + [:i]
	if T == tmp:
		print('Yes')
		break
print('No') 

### FIXED CODE ###

S = list(input())
T = list(input())

for i in range(len(S)):
	tmp = S[i:] + S[:i]
	if T == tmp:
		print('Yes')
		exit()
print('No')
hn_kz={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
kz_hn={}
n,m,*kzs=map(int,open(0).read().split())
#本数から数を求める辞書を作る。同じ本数の数は大きい方を取る
for kz in kzs:
    ah=hn_kz[kz]
    if ah in kz_hn:
        kz_hn[ah]=max(kz_hn[ah],kz)
    else:
        kz_hn[ah]=kz
#最小の本数をhmnに格納
hmn=min(kz_hn.keys())
#まず、最小の本数の数だけで桁[本数]の辞書を作る
kt_hn={kt*hmn:kt for kt in range(n//hmn+1)}
#本数から桁数を求める関数
inf=100
def keta(hn):
    if hn in kt_hn:
        return kt_hn[hn]
    elif hn<0:
        return -inf
    else:
        maxketa=-inf
        for hni in kz_hn.keys():
            newkt=keta(hn-hni)+1
            if newkt>maxketa:
                maxketa=newkt
        kt_hn[hn]=maxketa
        return maxketa
#目的の数を作る
ans=""
nokori=n
while nokori>0:
    for kh in sorted(kz_hn.items(),key=lambda xkh:xkh[1],reverse=True):
        if keta(nokori-kh[0])==keta(nokori)-1:
            ans+=str(kh[1])
            nokori-=kh[0]
            break
print(ans)

### FIXED CODE ###

def smax(s1, s2):
    if s1=="N":
        if s2[0]=="N":
            return "N"
        else:
            return s2
    if s2[0] == "N":
        return s1
    l1 = len(s1)
    l2 = len(s2)
    if l1 == l2:
        return max(s1, s2)
    if l1 > l2:
        return s1
    return s2

hon = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
n, m = map(int, input().split())
aa = list(map(int, input().split()))
dp = ["N"] * (n + 1)
dp[0]=""
for i in range(2, n + 1):
    for a in aa:
        if i - hon[a] < 0: continue
        dp[i] = smax(dp[i], dp[i - hon[a]] + str(a))
print(dp[-1])
h, w = map(int, input().split())
s = ["."+input()+"." for i in range(h)]
s = ["."*w] + s + ["."*w]

for i in range(1,h+1):
  for j in range(1,w+1):
    if s[i][j] == "#":
      if s[i][j+1] == s[i][j-1] == s[i+1][j] == s[i-1][j] == ".":
        print("No")
        exit()

print("Yes")

### FIXED CODE ###

h, w = map(int, input().split())
s = [input() for i in range(h)]
flag = True

for i in range(h):
  for j in range(w):
    if s[i][j] == "#":
      top = max(0, i-1)
      bottom = min(h-1, i+1)
      right = min(w-1, j+1)
      left = max(0, j-1)
      if s[i][right] != "#" and s[i][left] != "#" and s[top][j] != "#" and s[bottom][j] != "#":
        flag = False
        break
  if flag == False:
    break

if flag:
  print("Yes")
else:
  print("No")
N, W = map(int, input().split())
W = []
V = []

for _ in range(N):
  w, v = map(int, input().split())
  W.append(w)
  V.append(v)

Ans = [[0 for _ in range(W+1)] for _ in range(N)]

for i in range(W+1):
  if i >= W[0]
  Ans[0][i] = V[0]

for i in range(1, N):
  for w in range(W+1):
    Ans[i][w] = max(Ans[i-1][w-W[i]], Ans[i-1][w])

print(max(Ans[N-1]))

### FIXED CODE ###

import sys
import pdb
input = sys.stdin.readline

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

inf = 1e10

# Value[i番目までの品番][重さj以下]
Value = [[-inf for _ in range(W+1)] for __ in range(N)]

for load in range(W+1):
  if load < ws[0]:
    # 1番目の品物を入れようがなければスキップ
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:
      # pdb.set_trace()
      # print(num, load, ws[num], vs[num])
      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
    else:
      Value[num][load] = max(Value[num][load], Value[num-1][load])

print(Value[N-1][W])