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

# coding: utf-8
import queue

row, col = map(int, input().split(' '))
maze = [list(input()) for _ in range(row)]

                
def BPS(si, sj, gi, gj):
    global done
    done = [[0 for _ in range(col)] for _ in range(row)]
    q = queue.Queue()
    q.put((si, sj, 0))
    around = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    while not q.empty():
        i, j, cnt = q.get()
        done[i][j] = 1
        for ar in around:
            di, dj = ar[0], ar[1]
            i_n, j_n = i + di, j + dj
            if (i_n >= 0 and i_n < row and j_n >= 0 and j_n < col) == False:
                continue
            if maze[i_n][j_n] == '#':
                continue
            if done[i_n][j_n] == 1:
                continue
            if done[i_n][j_n] == 2:
                continue
            q.put((i_n, j_n, cnt + 1))
            done[i_n][j_n] = 2
        if i == gi and j == gj:
            return cnt
    return 0
            
            
def main():        
    maxv = 0
    for i in range(row):
        for j in range(col):
            for k in range(row):
                for l in range(col):
                    if i == k and j == l:
                        continue
                    maxv = max(maxv, BPS(i,j,k,l))
    print(maxv)
                    
                
                    
    
main()


### FIXED CODE ###

# coding: utf-8
import queue

row, col = map(int, input().split(' '))
maze = [list(input()) for _ in range(row)]

                
def BPS(si, sj):
    done = [[0 for _ in range(col)] for _ in range(row)]
    q = queue.Queue()
    q.put((si, sj, 0))
    around = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    maxv = 0
    while not q.empty():
        i, j, cnt = q.get()
        done[i][j] = 1
        for ar in around:
            di, dj = ar[0], ar[1]
            i_n, j_n = i + di, j + dj
            if (i_n >= 0 and i_n < row and j_n >= 0 and j_n < col) == False:
                continue
            if maze[i_n][j_n] == '#':
                continue
            if done[i_n][j_n] == 1:
                continue
            if done[i_n][j_n] == 2:
                continue
            maxv = max(maxv, cnt + 1)
            q.put((i_n, j_n, cnt + 1))
            done[i_n][j_n] = 2
        
    return maxv
            
            
def main():        
    maxv = 0
    for i in range(row):
        for j in range(col):
            if maze[i][j] == '#':
                continue
            maxv = max(maxv, BPS(i,j))
    print(maxv)
                    
                
                    
    
main()
### BUGGY CODE ###


n, m = list(map(int, input().split()))
aaa = list(int(input()) for i in range(m))

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7

for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1])
print(dp[n] % MOD)


### FIXED CODE ###

n, m = list(map(int, input().split()))
broken = [False] * (n + 1)
for _ in range(m):
    broken[int(input())] = True

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if not broken[1] else 0
MOD = 10 ** 9 + 7

for i in range(2, n + 1):
    if not broken[i - 1]:
        dp[i] += (dp[i - 1])
    if not broken[i - 2]:
        dp[i] += (dp[i - 2])
    dp[i] %= MOD

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

n = int(input())
all_set = set([c for c in range(1,n+1)])
node_col = [set() for _ in range(n)]
maxc = 0
anslist = []
for i in range(n-1):
    a,b = map(int,input().split())
    abset = node_col[a-1] | node_col[b-1]
    all_m_ab = all_set - abset
    minc = min(all_m_ab)
    node_col[a-1].add(minc)
    node_col[b-1].add(minc)
    anslist.append(minc)
    maxc = max(maxc,minc)
print(maxc)
for p in anslist:print(p)

### FIXED CODE ###

import queue
n = int(input())
tree_node = [set() for _ in range(n)]
hen = []
hen_col = {}
for i in range(n-1):
    a,b = map(int,input().split())
    tree_node[a-1].add(b)
    hen.append([a,b])
    hen_col[str(a)+'-'+str(b)] = 0
q = queue.Queue()
q.put(1)
parent_node = [0] * n
parent_color = [0] * n
maxcol = 0
while not q.empty():
    col = 0
    nod = q.get()
    for i,c in enumerate(tree_node[nod-1]):
        if i+1 == parent_color[nod-1]:col+=1
        tempcol = i+1+col
        parent_color[c-1]=tempcol
        maxcol = max(maxcol,tempcol)
        q.put(c)
        l = min(nod,c)
        r = max(nod,c)
        hen_col[str(l)+'-'+str(r)] = tempcol
        parent_node[c-1] = nod

print(maxcol)
for t in hen:
    tempstr = str(t[0])+'-'+str(t[1])
    print(hen_col[tempstr])
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    x, y = [int(x) for x in input().split()]
    a.append([x, y])
    a.sort(reverse=True)

b = 0
for i in range(n // 2):
    b += a[2 * i][0] - a[2 * i + 1][1] 
if n % 2 == 1:
    b += a[len(a) - 1][0]

print(b)


### FIXED CODE ###

n = int(input())
#z = [[int(x) for x in input().split()] for i in range(n)]
z = []
t = 0
for i in range(n):
    x, y = [int(x) for x in input().split()]
    t += y
    z.append(x + y)
z.sort(reverse=True)

s = 0
for i in range(n // 2):
    s += z[2 * i]
if n % 2 == 1:
    s += z[len(z) - 1]

print(s - t)

#アルゴリズムが間違っている
### BUGGY CODE ###

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


def ave(num):
    return (1 + num) / 2


ave_list = []
max_sum = 0
Kdaice_list = []
for i in range(N - K + 1):
    K_sum = sum(p_list[i:i + K])
    if max_sum < K_sum:
        max_sum = K_sum
        Kdaice_list = []
        max_ave = 0
        for d in p_list[i:i + K]:
            max_ave += ave(d)
        ave_list.append(max_ave)

print(max(ave_list))


### FIXED CODE ###

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

c_s_list = [0] #Cumulative sum_list
c_sum = 0 #Cumulative sum
for dice in p_list:
    average = (dice + 1) / 2 #ダイスの期待値
    c_sum += average
    c_s_list.append(c_sum)

ans = 0
for i in range(N-K+1):
    tmp = c_s_list[i+K] - c_s_list[i]
    if tmp >= ans:
        ans = tmp
print(ans)
### BUGGY CODE ###

N = int(input())

for i in range(1,N+1):
  count = 0
  if i < 6:
    print('0')
  elif i == 6:
    print('1')
  else:
    for j in range(1,i):
      if (6*(j**2))==i:
        count += 1
      else:
        for k in range(1,i):
          if (3*(j**2)+2*j*k+k**2)==i:
            count += 1
          else:
            for l in range(1,i):
              if (j**2+k**2+l**2+j*k+k*l+l*j)==i:
                count += 1
        
    print(count)
    

### FIXED CODE ###

N = int(input())
l = [0]*N

for x in range(1,101):
  for y in range(1,101):
    for z in range(1,101):
      if (x**2+y**2+z**2+x*y+y*z+z*x)<=N:
        l[x**2+y**2+z**2+x*y+y*z+z*x-1]+=1

for i in l:
  print(i)
### BUGGY CODE ###

n = int(input())
s_li=[input() for i in range(n)]
new_li=[]
for i in range(n):
  s_li[i]=sorted(list(s_li[i]))
ans = 0
for i in range(n):
  for j in range(i+1,n):
    if s_li[i] == s_li[j]:
      ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
dic = {}
ans = 0
for i in range(n):
  li_1 = list(input())
  li_1.sort()
  word = "".join(li_1)
  if word in dic:
    dic[word] += 1
  else:
    dic[word] = 1
for key in dic:
  s = dic[key]
  ans += s*(s-1)//2
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a_set = sorted(list(set(a)), reverse=True)
cnt, ans = 0, 1

for i in range(len(a_set)):
    if a.count(a_set[i]) > 3 and cnt == 0:
        print(a_set[i]**2)
        exit()
    if a.count(a_set[i]) > 1:
        ans *= a_set[i]
        cnt += 1
    if cnt == 2:
        print(ans)
        exit()

print(0)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = set()
cands = []

for i in a:
    if i in s:
        cands.append(i)
        s.remove(i)
    else:
        s.add(i)

x = sorted(cands, reverse=True)
if len(x) < 2:
    print(0)
else:
    print(x[0]*x[1])
### BUGGY CODE ###

N = int(input())
flag = 0

for n in range(N):
    count = 0
    for x in range(1,100):
        for y in range(1,100):
            for z in range(1,100):
                culc = x**2 + y**2 + z**2 + x*y + y*z + z*x - (n + 1)
                if culc == 0:
                    count += 1
                elif culc > 0:
                    break
                elif culc < 0:
                    continue

    print(count)

### FIXED CODE ###

N = int(input())
ans = [0] * 11000

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            culc = x*x + y*y + z*z + x*y + y*z + z*x
            if culc <= 11000:
                ans[culc] += 1

for i in range(1,N+1):
    print(ans[i])
### BUGGY CODE ###

# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    # all = list(map(int, sys.stdin.read().split())
    #N, *A = map(int, open(0))
    #N = int(input())
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 0
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))
        max_m = max(max_m, a)

    max_m *= N-1

    CD = [[0,0]]
    for _ in range(N):
        c,d = list(map(int, sysread().split()))
        CD.append([c,d])

    queue = []
    # (time, node, rest-coin)
    if S > max_m:
        S = max_m
    heappush(queue, (0, 1, S))

    state = [[float('inf')] * (max_m+1) for _ in range(N+1)]

    while queue:
        time, node, coin = heappop(queue)
        if state[node][coin] < time: continue
        c, d = CD[node]
        if coin + c <= max_m and time + d < state[node][coin+c]:
            state[node][coin+c] = time + d
            heappush(queue, (time+d, node, coin+c))
        for n_node, n_time, n_coin in to[node]:
            if coin < n_coin:continue
            if state[n_node][coin-n_coin] < n_time + time:continue
            state[n_node][coin - n_coin] = n_time + time
            heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in state[2:]:
        print(min(s))

if __name__ == "__main__":
    run()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
read = sys.stdin.read
 
n,m,s = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = [int(i) for i in readline().split()]
    u -= 1
    v -= 1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
 
 
cd = [int(i) for i in read().split()]
c = cd[::2]
d = cd[1::2]
 
 
from heapq import *
INF = 1<<61
M = 2500
if s >= M: s = M-1
dist = [[INF]*M for _ in range(n)] #startからの最短距離
dist[0][s] = 0
q = [(0,s,0)] #(そこまでの距離、銀の枚数、点)
 
while q:
    dv,num,v = heappop(q)
    if dist[v][num] < dv: continue
    if num+c[v] < M and dv+d[v] < dist[v][num+c[v]]:
        dist[v][num+c[v]] = dv + d[v]
        heappush(q, (dv + d[v], num+c[v] ,v))
    for to,a,b in g[v]:
        if num >= a and dv + b < dist[to][num-a]:
            dist[to][num-a] = dv + b
            heappush(q, (dv + b, num-a ,to))
    #print(q)
 
for i in range(1,n):
    print(min(dist[i]))
### BUGGY CODE ###

from fractions import gcd

a, b = map(int, input().split())

ans = 0
tmp = 1
g = gcd(a,b)
while g > 1:
    for i in range(tmp+1,g//2):
        if g%i == 0:
            ans += 1
            tmp = i
            while g%i == 0:
                g //= i
            break
    else:
        # もうgでしか割れないはず
        ans += 1
        break
print(ans+1)


### FIXED CODE ###

from fractions import gcd
from math import sqrt, ceil

a, b = map(int, input().split())

ans = 0
tmp = 1
g = gcd(a,b)
while g > 1:
    for i in range(tmp+1,ceil(sqrt(g))):
        if g%i == 0:
            ans += 1
            tmp = i
            while g%i == 0:
                g //= i
            break
    else:
        # もうgでしか割れないはず
        ans += 1
        break
print(ans+1)
### BUGGY CODE ###

a, b, x = map(int, input().split())
print([n%x==0 for n in range(a, b+1)].count(True))

### FIXED CODE ###

a, b, x = map(int, input().split())
print(b//x - (-(-a//x)) + 1)
### BUGGY CODE ###

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

n, m = map(int, input().split())
ok =  [int(i) for i in range(1, n+1)]
answer = 0
for i in range(m):
    a, b = map(int, input().split())
    l = [int(n) for n in range(a, b+1)]
    ok = list(set(ok) & set(l))

print(len(ok))

### FIXED CODE ###

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

n, m = map(int, input().split())
l = []
r = []
answer = 0
for i in range(m):
    a, b = map(int, input().split())
    l.append(a)
    r.append(b)
min_ok = max(l)
max_ok = min(r)
answer = max_ok - min_ok + 1
if answer < 0:
    answer = 0
print(answer)
### BUGGY CODE ###

from collections import defaultdict
from collections import deque
dd = defaultdict(list)
pq = defaultdict(int)
 
N, Q = map(int, input().split())
 
for _ in range(N-1):
    a,b = map(int, input().split())
    dd[a].append(b)
    dd[b].append(a)
 
for _ in range(Q):
    p,q = map(int, input().split())
    pq[p] += q
    
answer = [0]*N
queue = deque()
visited = {}
visited[1] = 1
queue.append(1)
 
while queue != deque():
    tmp = queue.popleft()
    answer[tmp-1] += pq[tmp]
    for i in dd[tmp]:
        if not i in visited:
            visited[i] = 1
            queue.append(i)
            answer[i-1] += answer[tmp-1]
            
print(*answer)

### FIXED CODE ###

def main():
    from collections import defaultdict
    from collections import deque
    import sys
    input = sys.stdin.readline
    dd = defaultdict(list)
    pq = defaultdict(int)

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

    for _ in range(N-1):
        a,b = map(int, input().split())
        dd[a].append(b)

    for _ in range(Q):
        p,q = map(int, input().split())
        pq[p] += q
    
    answer = [0]*N
    queue = deque()
    queue.append(1)

    while queue != deque():
        tmp = queue.popleft()
        answer[tmp-1] += pq[tmp]
        for i in dd[tmp]:
            queue.append(i)
            answer[i-1] += answer[tmp-1]
            
    print(*answer)

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

from collections import deque
N, Q = map(int, input().split())
nodes = [0]*(N+1)
tree = [set() for _ in range(N+1)]
for i in range(1, N):
  a, b = map(int, input().split())
  tree[a].add(b)

def add(p, x):
  dq = deque()
  dq.append(p)
  while len(dq) > 0:
    p = dq.popleft()
    nodes[p] += x
    for np in tree[p]:
      dq.append(np)

for i in range(Q):
  p, x = map(int, input().split())
  add(p, x)
print(" ".join([str(i) for i in nodes[1:]]))

### FIXED CODE ###

N, Q = map(int, input().split())
tree = [[] for i in range(N)]

for i in range(N-1):
  a, b = map(int, input().split())
  tree[a-1].extend([b])

nodes = [0]*N
for _ in range(Q):
  p, x = map(int, input().split())
  nodes[p-1]+=x

for i in range(N-1):
  for j in tree[i]:
    nodes[j-1]+=nodes[i]
print(" ".join(list(map(str, nodes))))
### BUGGY CODE ###

N, M, Q = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for _ in range(M)]
PQ = [[int(_) for _ in input().split()] for _ in range(Q)]

dp = [[0] * N for _ in range(N)]
for lr in LR:
    dp[lr[0] - 1][lr[1] - 1] += 1
for pq in PQ:
    print(sum([sum(dp[i][i:pq[1]]) for i in range(pq[0] - 1, pq[1])]))


### FIXED CODE ###

N, M, Q = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for _ in range(M)]
PQ = [[int(_) for _ in input().split()] for _ in range(Q)]

cumsum = [[0] * (N+2) for _ in range(N+1)]
for lr in LR:
    cumsum[lr[0]][lr[0]] += 1
    if lr[1] < N:
        cumsum[lr[0]][lr[1]+1] -= 1
for i in range(N+1):
    for j in range(i, N):
        cumsum[i][j+1] += cumsum[i][j]
for pq in PQ:
    print(sum([cumsum[i][i]-cumsum[i][pq[1]+1]
               for i in range(pq[0], pq[1]+1)]))
### BUGGY CODE ###

import time
start=time.time()
import random
d=int(input())
c=list(map(int, input().split()))
s=[list(map(int, input().split())) for _ in range(d)]
t=[0]*26
ans=0
solution=[]
for i in range(1,d+1):
  tmp=s[i-1].index(max(s[i-1]))
  solution.append(tmp)
  t[tmp]=i
  ans+=s[i-1][tmp]
  for j in range(26):
    ans-=c[j]*(i-t[j])
now=time.time()
while now-start<1.5:
  di=random.randrange(1,d+1)
  qi=random.randrange(1,27)
  old=solution[di-1]
  solution[di-1]=qi-1
  tmp2=ans
  for _ in range(26):
    tmp2=tmp2-s[di-1][old]+s[di-1][qi-1]
  if ans-tmp2>=0:
    solution[di-1]=old
    continue
  else:
    ans=tmp2
  now=time.time()
for k in solution:
  print(k+1)

### FIXED CODE ###

d=int(input())
c=list(map(int, input().split()))
s=[list(map(int, input().split())) for _ in range(d)]
t=[0]*26
ans=0
for i in range(1,d+1):
  tmp=s[i-1].index(max(s[i-1]))
  print(tmp+1)
### BUGGY CODE ###

from bisect import bisect
n = int(input())
A = []
for i in range(n):
 A.append(int(input()))
 
 L = [None for i in range(n)]
def LIS():
    L[0] = A[0]
    length = 0
    for i in range(n):
        if L[length] < A[i]:
            length += 1
            L[length] = A[i]
        else:
            if A[i] in L: continue
            j = bisect(L, A[i], 0, length)
            L[j] = A[i]
    return length + 1

print(LIS())

### FIXED CODE ###

from bisect import bisect_left
import sys

n = int(input())
A = [int(i.rstrip("\n")) for i in sys.stdin.readlines()]

def LIS():
    L = A[:1]
    for i in A[1:]:
        if L[-1] < i:
            L.append(i)
        else:
            j = bisect_left(L, i)
            L[j] = i
    return len(L)

print(LIS())
### BUGGY CODE ###

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

graph = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if S[i][j] == 1: graph[i].append(j)

from collections import deque

ans_tmp = 0
possible = True
for home in range(N):
    iswhite = [None] * N
    q = deque([(home, False, 0)])
    while len(q) > 0:
        src, white, depth = q.popleft()
        # print("##", src, white, depth)
        iswhite[src] = white
        ans_tmp = max(ans_tmp, depth)
        for dst in graph[src]:
            # print("###", dst, iswhite[dst])
            if iswhite[dst] == None:
                q.append((dst, (white != True), depth + 1))
            elif white == iswhite[dst]:
                possible = False
                break
            else:
                continue
        #
        if possible == False:
            break
    
if possible:
    print(ans_tmp + 1)
else:
    # print("#", iswhite)
    print(-1)

### FIXED CODE ###

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

graph = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if S[i][j] == 1: graph[i].append(j)

from collections import deque

ans_tmp = 0
possible = True
for home in range(N):
    iswhite = [None] * N
    q = deque([(home, False, 0)])
    iswhite[home] = False
    while len(q) > 0:
        src, white, depth = q.popleft()
        # print("##", src, white, depth)
        if depth > ans_tmp:
            # home = src
            ans_tmp = depth
        #
        for dst in graph[src]:
            # print("###", dst, iswhite[dst])
            if iswhite[dst] == None:
                white_dst = (white != True)
                q.append((dst, white_dst, depth + 1))
                iswhite[dst] = white_dst
            elif white == iswhite[dst]:
                possible = False
                break
            else:
                continue
        #
        if possible == False:
            break
    
if possible:
    print(ans_tmp + 1)
else:
    # print("#", iswhite)
    print(-1)
### BUGGY CODE ###

s=input()
ans=0
while s.count('AABCBC')>0:
    ans+=s.count('AABCBC')*4
    s=s.replace('AABCBC','BCBCAA')
while s.count('ABCBC')>0:
    ans+=s.count('ABCBC')*2
    s=s.replace('ABCBC','BCBCA')
while s.count('AABC')>0:
    ans+=s.count('AABC')*2
    s=s.replace('AABC','BCAA')
while s.count('ABC')>0:
    ans+=s.count('ABC')
    s=s.replace('ABC','BCA')
print(ans)

### FIXED CODE ###

import re
s=input()
ss=s.replace('BC','D')
sss=re.split('[BC]',ss)
ans=0
for i in sss:
    acnt=0
    for g in i:
        if g=='A':
            acnt+=1
        else:
            ans+=acnt
print(ans)
### BUGGY CODE ###

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

def div(x):
    div_list = []
    for i in range(1,x//N+2):
        if x%i == 0 and x//i >= N:
            div_list.append(i)
    return div_list

a = div(M)
print(a[-1])

### FIXED CODE ###

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

d = int(M**(1/2))
div_list = []
while d >= 1:
    if M%d == 0:
        div_list.append(d)
        div_list.append(M//d)
    d -= 1

div_list.sort(reverse = True)
for i in range(len(div_list)):
    if div_list[i] <= M//N:
        print(div_list[i])
        break
### BUGGY CODE ###

def main():
    n, m, q = map(int, input().split())
    trains = [list(map(int, input().split())) for _ in range(m)]
    questions = [list(map(int, input().split())) for _ in range(q)]

    for question in questions:
        a, b = question
        # result = [train for train in trains if a <= train[0] and train[1] <= b]
        result = list(filter(lambda x: a <= x[0] and x[1] <= b, trains))
        print(len(result))

if __name__ == '__main__':
    main()


### FIXED CODE ###

n, m, q = map(int, input().split())
cities = [[0 for _ in range(n+1)] for _ in range(n+2)]
trains = [list(map(int, input().split())) for _ in range(m)]
quests = [list(map(int, input().split())) for _ in range(q)]

for train in trains:
    x, y = train[0], train[1]
    cities[x][y] += 1

for i in range(n):
    for j in range(1, n-i+1):
        x = j + i
        cities[j][x] += cities[j][x-1] + cities[j+1][x] - cities[j+1][x-1]

for quest in quests:
    p, q = quest[0], quest[1]
    print(cities[p][q])
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())
table = []
for i in range(N):
  a,b,c = map(int, input().split())
  table.append([a,b,c])
inf = 10**9
dp = [[[inf]*401 for i in range(401)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(1,N+1):
  a,b,c = table[i-1]
  for j in range(401):
    for k in range(401):
      dp[i][j][k] = dp[i-1][j][k]
      if 400>=j-a>=0 and 400>=k-b>=0:
        dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)
ans = 10**9
i = 1
while max(Ma,Mb)*i <= 400:
  ans = min(ans,dp[N][Ma*i][Mb*i])
  i += 1
if ans == 10**9:
  ans = -1
print(ans)

### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
table = []
for i in range(N):
  a,b,c = map(int, input().split())
  table.append([a,b,c])
inf = 10**9
dp = [[[inf]*401 for i in range(401)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(1,N+1):
  a,b,c = table[i-1]
  for j in range(401):
    for k in range(401):
      dp[i][j][k] = dp[i-1][j][k]
      if 400>=j-a>=0 and 400>=k-b>=0:
        dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)
ans = 10**9
i = 1
while max(Ma,Mb)*i <= 400:
  ans = min(ans,dp[N][Ma*i][Mb*i])
  i += 1
if ans == 10**9:
  ans = -1
print(ans)
### BUGGY CODE ###

import math
def comb(n,r):
	if n < r:
		return 0
	return int(math.factorial(n) / (math.factorial(r) * math.factorial(n-r)))


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

a = sorted(a)

r = 0
maxV = 0
for i in range(max(0,n//2-2),min(n-1,n//2+2)):
	curr = comb(a[-1],a[i])
	if maxV < curr:
		r = a[i]
		maxV = curr

print(a[-1], r)

### FIXED CODE ###

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

a = sorted(a)

r = 0
minV = 10**10
for i in range(n-1):
	curr = abs(a[-1] / 2 - a[i])
#	print(a[-1],a[i],curr)
	if minV > curr:
		r = a[i]
		minV = curr

print(a[-1], r)
### BUGGY CODE ###

H, N = map(int, input().split())
A = [None] * N
B = [None] * N

for n in range(N):
    A[n], B[n] = map(int, input().split())

lim = H + max(A)
dp = [10**8] * lim
dp[0] = 0

for h in range(lim):
    for n in range(N):
        rem = h - A[n]
        cns = B[n]

        if 0 < rem:
            cns += dp[rem]
        dp[h] = min(cns, dp[h])

print(min(dp[H:lim]))


### FIXED CODE ###

H, N = map(int, input().split())
A = [None] * N
B = [None] * N

for n in range(N):
    A[n], B[n] = map(int, input().split())

lim = H + max(A)
dp = [10**8] * lim
dp[0] = 0

for h in range(lim):
    for n in range(N):
        rem = h - A[n]
        cns = B[n]

        if 0 < rem:
            cns += dp[rem]
        dp[h] = min(cns, dp[h])

print(min(dp[H:lim]))