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

h, n = map(int, input().split())
dp = [1000000000] * (h+1)
dp[0] = 0
for i in range(n):
    a, b = map(int, input().split())
    for j in range(h):
        nj = min(j + a, h)
        dp[nj] = min(dp[nj], dp[j] + b)
print(dp[h])

### FIXED CODE ###

h, n = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
###一次元DP
dp = [100000000] * (h+1)
dp[0] = 0
for i in range(1, h+1):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        # print(i, j)
        temp = i - a
        if temp < 0:
            temp = 0
        need_magic = dp[temp] + b
        if need_magic < dp[i]:
            dp[i] = need_magic
        # dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
        # print(i, j, a, b, dp)
print(dp[-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

s_len, n = map(int, input().split())
s = input().rstrip()
for i in range(n):
  a, b = map(int, input().split())
  s_slice = s[a-1:b]  
  count = sum([s_slice[i:2+i]=="AC" for i in range(len(s_slice)-1)])
  print(count)
  


### FIXED CODE ###

import sys
input = sys.stdin.readline

import bisect
left = bisect.bisect_left
right = bisect.bisect_right 

n, q = list(map(int, input().split()))
s = input()
lr = [list(map(int, input().split())) for i in range(q)]
a = [i for i in range(n-1) if s[i:i+2]=="AC"]

for i in range(q):
  left_index = left(a, lr[i][0]-1)      
  right_index = right(a, lr[i][1]-2)  
  print(right_index - left_index)
### BUGGY CODE ###

import sys


def input(): return sys.stdin.readline().rstrip()


S = input()
T = input()
dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]
# dp[i][j] := i,j までの最大のもの。(length)
for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            if dp[i+1][j] >= dp[i][j+1]:
                dp[i+1][j+1] = dp[i+1][j]

            elif dp[i+1][j] < dp[i][j+1]:
                dp[i+1][j+1] = dp[i][j+1]
X, Y = len(S), len(T)
ans = []
while dp[X][Y]:
    if S[X-1] == T[Y-1]:
        ans.append(S[X-1])
        X -= 1
        Y -= 1
    else:
        if dp[X-1][Y] >= dp[X][Y-1]:
            X -= 1
        else:
            Y -= 1
            continue
ans.reverse()
print("".join(ans))

### FIXED CODE ###

import sys


def input(): return sys.stdin.readline().rstrip()


S = input()
T = input()
dp = [[0]*(len(T)+1) for j in range(len(S)+1)]
# dp[i][j] := i,j までの最大のもの。(length)
for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            if dp[i+1][j] >= dp[i][j+1]:
                dp[i+1][j+1] = dp[i+1][j]

            elif dp[i+1][j] < dp[i][j+1]:
                dp[i+1][j+1] = dp[i][j+1]
X, Y = len(S), len(T)
ans = []
while dp[X][Y]:
    if S[X-1] == T[Y-1]:
        ans.append(S[X-1])
        X -= 1
        Y -= 1
    else:
        if dp[X-1][Y] >= dp[X][Y-1]:
            X -= 1
        else:
            Y -= 1
            continue
ans.reverse()
print("".join(ans))
### BUGGY CODE ###

n=int(input())
s=input()
cnt=0
r=s.count("R")
g=s.count("G")
b=s.count("B")

ans=r*g*b

for i in range(n):
    for j in range(n):
        if s[i]!=s[j]:
            if j-i<=n//2:
                if i<j:
                    for k in range(n):
                        if s[k]!=s[j] and s[i]!=s[k]:   
                            if j<k:
                                if j-i==k-j:
                                    ans-=1

            else:
                break        
print(ans)
        


### FIXED CODE ###

n=int(input())
s=input()
cnt=0
r=s.count("R")
g=s.count("G")
b=s.count("B")

ans=r*g*b

for i in range(n):
    for j in range(n):
        if s[i]!=s[j]:
            if j-i<=n//2:
                if i<j:
                    d=j-i
                    k=j+d
                    if k<n:
                        if s[k]!=s[j] and s[i]!=s[k]:
                            ans-=1
                        

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

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
def resolve():
    n=int(input())
    A=[tuple(map(lambda x:int(x)-1,input().split())) for _ in range(n)]

    N=0
    V={}
    for i in range(n):
        for j in range(i+1,n):
            V[(i,j)]=N
            N+=1

    E=[[] for _ in range(N)] # N=n*(n-1)//2
    for i in range(n):
        for j in range(n-2):
            u=V[(min(i,A[i][j]),max(i,A[i][j]))]
            v=V[(min(i,A[i][j+1]),max(i,A[i][j+1]))]
            E[u].append(v)

    # longest path problem
    dp=[None]*N
    visited=[0]*N

    def dfs(v):
        if(dp[v] is not None): return dp[v]
        visited[v]=1
        res=0
        for nv in E[v]:
            if((dp[nv] is None) and visited[nv]):
                print(-1)
                exit(0)
            res=max(res,dfs(nv)+1)
        dp[v]=res
        return res

    print(max(dfs(v) for v in range(N))+1)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    match=[[0]*n for _ in range(n)]
    V=0 # V=n(n-1)/2
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        match[i][j]=V
        V+=1

    def toID(i,j):
        if(i>j): i,j=j,i
        return match[i][j]

    E=[[] for _ in range(V)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(1,n-1):
            E[toID(i,A[j-1])].append(toID(i,A[j]))
    # あとは頂点VのグラフをdfsしてLongest pathの長さを求める
    # -1: unchecked, -2: checked and uncalculated
    dp=[-1]*V
    flag=True
    def dfs(v):
        global flag
        dp[v]=-2
        length=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            if(dp[nv]==-1):
                dfs(nv)
            length=max(length,dp[nv]+1)
        dp[v]=length
    # calculate
    for i in range(V): dfs(i)
    print(max(dp)+1 if(flag) else -1)
resolve()
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
m=int(input())
b=list(map(int, input().split()))
b2=set(b)
ans='YES'
for i in b:
    if a.count(i)<b.count(i):
        ans='NO'
        break
print(ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int, input().split()))
m=int(input())
b=list(map(int, input().split()))
ans='YES'
a1=Counter(a)
b1=Counter(b)
for i in b:
    if a1[i]<b1[i]:
        ans='NO'
        break
print(ans)
### BUGGY CODE ###

def nibun(x,s,N):
    l=0
    r=N-1
    while r!=l+1:
        c=(l+r)//2
        if s[c]>x:
            r=c
        elif s[c]<x:
            l=c
        else:
            return c
    if (s[r]-x)>(x-s[l]):
        return l
    return r
import numpy as np
A,B,Q=map(int,input().split())
s=[0 for i in range(A)]
t=[0 for i in range(B)]
x=[0 for i in range(Q)]
s=np.array(s)
t=np.array(t)
x=np.array(x)
for i in range(A):
    s[i]=int(input())
for i in range(B):
    t[i]=int(input())
for i in range(Q):
    x[i]=int(input())

for X in x:
    l1=abs(X-t[nibun(X,t,B)])
    if -l1 in X-t:
        l1=-l1
    l2=abs(X-s[nibun(X,s,A)])
    if -l2 in X-s:
        l2=-l2
    print(min(abs(l1)+abs(X-l1-s[nibun(X-l1,s,A)]),abs(l2)+abs(X-l2-t[nibun(X-l2,t,B)])))


### FIXED CODE ###

import bisect
INF=10**18
A,B,Q=map(int,input().split())
s=[int(input()) for i in range(A)]
t=[int(input()) for i in range(B)]
s=[-INF]+s+[INF]
t=[-INF]+t+[INF]
for q in range(Q):
    X=int(input())
    t1=bisect.bisect_right(t,X)
    s1=bisect.bisect_right(s,X)
    res=INF
    for T in [t[t1],t[t1-1]]:
        for S in [s[s1],s[s1-1]]:
            ans1=abs(X-T)+abs(S-T)
            ans2=abs(X-S)+abs(S-T)
            res=min(res,ans1,ans2)
    print(res)
### BUGGY CODE ###

N = int(input())
counter = 0
for A in range(1,N):
  for B in range(1,N//A+1):
    if 0< N - A*B:
        counter += 1
print(counter)

### FIXED CODE ###

N = int(input())
counter = 0
for A in range(1,N):
  for B in range(1,N//A+1):
    if 0 < A*B < N:
        counter += 1
print(counter)
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
cnt = 0
for i in range(n//r + 1):
    for j in range(n//g + 1):
        t = n - i*r - j*g
        if t%b==0 and t//b>=0:
            cnt += 1
print(cnt)

### FIXED CODE ###

r,g,b,n = map(int,input().split())
cnt = 0
for i in range(n//r + 1):
    for j in range(n//g + 1):
        t = n - i*r - j*g
        if t%b==0 and t//b>=0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

from copy import copy, deepcopy
from collections import Counter
from math import sqrt, floor, factorial
from itertools import permutations, combinations, combinations_with_replacement
from operator import mul
from functools import reduce
import bisect

MOD = 10**9 + 7
INF = float('inf')

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

#A = [0 for i in range(N)]
B = [0 for i in range(N)]

# print(A)
for _ in range(K):
    B = [0 for i in range(N)]
    for i in range(N):
        tmp = A[i]
        B[max(i-tmp, 0)] += 1
        idx = min(i+tmp+1, N)
        if idx != N:
            B[idx] -= 1
    # print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    # print(B)
    A = B.copy()
    if _ > 2 * int(sqrt(N)):
        break

L = " ".join([str(x) for x in A])
print(L)


### FIXED CODE ###

from copy import copy, deepcopy
from collections import Counter
from math import sqrt, floor, factorial, log
from itertools import permutations, combinations, combinations_with_replacement
from operator import mul
from functools import reduce
import bisect

MOD = 10**9 + 7
INF = float('inf')

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

#A = [0 for i in range(N)]
B = [0 for i in range(N)]

# print(A)
for _ in range(K):
    B = [0 for i in range(N)]
    for i in range(N):
        B[max(i-A[i], 0)] += 1
        idx = min(i+A[i]+1, N)
        if idx != N:
            B[idx] -= 1
    # print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    # print(B)
    A = B.copy()
    if _ > 10 * int(log(N)):
        break

L = " ".join([str(x) for x in A])
print(L)
### BUGGY CODE ###

N, K = map(int, input().strip().split())
result = 0
for a in range(K, N+1, K):
    for b in range(a, N + 1, K):
        for c in range(b, N + 1, K):
            if a == b and b == c:
                result += 1
            elif a == b or a == c or b == c:
                result += 3
            else:
                result += 6


if K % 2 == 1:
    print(result)
else:
    start = K // 2
    for a in range(start, N + 1, K):
        for b in range(a, N + 1, K):
            for c in range(b, N + 1, K):
                if a == b and b == c:
                    result += 1
                elif a == b or a == c or b == c:
                    result += 3
                else:
                    result += 6
    print(result)

### FIXED CODE ###

N, K = map(int, input().strip().split())
result = 0
num = N // K
result += num
if num == 2:
    result += num * (num - 1) * 3
elif num > 2:
    result += num * (num - 1) * 3
    result += num * (num - 1) * (num - 2)


if K % 2 == 1:
    print(result)
else:
    start = K // 2
    num = (N - start) // K + 1
    result += num
    if num == 2:
        result += num * (num - 1) * 3
    elif num > 2:
        result += num * (num - 1) * 3
        result += num * (num - 1) * (num - 2)
    print(result)
### BUGGY CODE ###

s=list(map(ord,list(input())))
k=int(input())

for i in range(len(s)):
    s[i]-=97

c=0
while k>0:
    if c==len(s)-1:
        s[c]=(s[c]+k)%26
        k=0
    elif s[c]+k>=26:
        k-=26-s[c]
        s[c]=0
        c+=1
    else:
        c+=1

seq=""
for i in range(len(s)):
    seq+=chr(s[i]+97)

print(seq)

### FIXED CODE ###

s=list(map(ord,list(input())))
k=int(input())

for i in range(len(s)):
    s[i]-=97

c=0
while k>0:
    if c==len(s)-1:
        s[c]=(s[c]+k)%26
        k=0
    elif s[c]==0:
        c+=1
    elif s[c]+k>=26:
        k-=26-s[c]
        s[c]=0
        c+=1
    else:
        c+=1

seq=""
for i in range(len(s)):
    seq+=chr(s[i]+97)

print(seq)
### BUGGY CODE ###

n = int(input())
A = []
i = 0 
while i < n:
    A.append(int(input())-1)
    i += 1
used_list = [0]
count = 0
t = 0
while count < n:
    t1 = A[t] 
    count += 1
    if t1 == 1:
        break
    if t1 in used_list:
        count = -1
        break
    used_list.append(t1)
    t = t1
print(count)

### FIXED CODE ###

n = int(input())
A = []
i = 0 
while i < n:
    A.append(int(input())-1)
    i += 1
used_list = [0]
count = 0
t = 0
while count < n:
    t1 = A[t] 
    count += 1
    if t1 == 1:
        break
#    if t1 in used_list:
#        count = -1
#        break
    used_list.append(t1)
    t = t1
if t1 != 1:
    count = -1
print(count)
### BUGGY CODE ###

from bisect import *
while 1:
    n, lmt = map(int, raw_input().split())
    if n == 0: break
    p = [input() for i in range(n)] + [0]
    p = sorted(set(i + j for i in p for j in p))
    s = bisect(p, lmt)
    print max(i + p[bisect(p[:s], lmt - i) - 1] for i in p[:s])

### FIXED CODE ###

from bisect import *
while 1:
    n, lmt = map(int, raw_input().split())
    if n == 0: break
    p = [input() for i in range(n)] + [0]
    p = sorted(set(i + j for i in p for j in p))
    s = bisect(p, lmt)
    print max(i + p[bisect(p, lmt - i) - 1] for i in p[:s])
### BUGGY CODE ###

def get_ac(n,q,s,l,r):
    pos = []

    for j in range(0,n-1):
        if s[j] == 'A' and s[j+1] == 'C':
            pos.append(j+1)

    p_len = len(pos)
    for i in range(q):
        left = l[i]
        right = r[i]
        count = 0
        for j in range(p_len):
            if left <= pos[j] and pos[j]+1 <= right:
                count += 1
        else:
            print count

if __name__ == '__main__':

    n,q = map(int,raw_input().split())
#    t1 = time.time()
    s = raw_input()

    l = [0]*q
    r = [0]*q

    for i in range(q):
        l[i],r[i] = map(int,raw_input().split())

#    t2 = time.time()
#    print('{0:.9f}'.format(t2 - t1))
    get_ac(n,q,s,l,r)

### FIXED CODE ###

def get_ac(n,q,s,l,r):
    pos = [0]*n

    for j in range(0,n-1):
        if s[j] == 'A' and s[j+1] == 'C':
            pos[j+1] = pos[j] + 1
        else:
            pos[j+1] = pos[j]

    for i in range(q):
        left = l[i]
        right = r[i]
        count = pos[right - 1] - pos[left - 1]

        print count

if __name__ == '__main__':

    n,q = map(int,raw_input().split())
#    t1 = time.time()
    s = raw_input()

    l = [0]*q
    r = [0]*q

    for i in range(q):
        l[i],r[i] = map(int,raw_input().split())

#    t2 = time.time()
#    print('{0:.9f}'.format(t2 - t1))
    get_ac(n,q,s,l,r)
### BUGGY CODE ###

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

max0, max1, count = [], 0, 0
for i in p:
    max0.append(i)
    max1 = i
    if max1 == 1:
        count += 1
        break
    elif min(max0) >= max1:
        count += 1
print(count)


### FIXED CODE ###

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

max0, max1, count = p[0], 0, 0
for i in p:
    max0 = min(max0, i)
    max1 = i
    if max1 == 1:
        count += 1
        break
    elif max0 >= max1:
        count += 1
print(count)
### BUGGY CODE ###

import numpy as np

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1 = np.full((2000,2000),-1)
dp2 = np.full((2000,2000),-1)
dp3 = np.full((2000,2000),-1)
dp4 = np.full((2000,2000),-1)



for i in range(h):
    for j in range(w-1,-1,-1):
        if s[i][j] == "#":
            dp2[i][j] = 0
        elif j == w-1:
            dp2[i][j] = 1
        else:
            dp2[i][j] = 1 + dp2[i][j+1]

for i in range(w):
    for j in range(h):
        if s[j][i] == "#":
            dp3[j][i] = 0
        elif j == 0:
            dp3[j][i] = 1
        else:
            dp3[j][i] = 1 + dp3[j-1][i]

for i in range(w):
    for j in range(h-1,-1,-1):
        if s[j][i] == "#":
            dp4[j][i] = 0
        elif j == h-1:
            dp4[j][i] = 1
        else:
            dp4[j][i] = 1 + dp4[j+1][i]

a = 1
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)

print(int(a))

### FIXED CODE ###

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1= []
dp2= [[-1 for i in range(w)] for j in range(h)]
dp3=[]
dp4=[[-1 for i in range(w)] for j in range(h)]


for i in range(h):
    dp1.append([])
    dp3.append([])
    for j in range(w):
        dp1[i].append(-1)
        dp3[i].append(-1)

        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

        if s[i][w-j-1] == "#":
            dp2[i][w-j-1] = 0
        elif w-j-1 == w-1:
            dp2[i][w-j-1] = 1
        else:
            dp2[i][w-j-1] = 1 + dp2[i][w-j]

        if s[i][j] == "#":
            dp3[i][j] = 0
        elif i == 0:
            dp3[i][j] = 1
        else:
            dp3[i][j] = 1 + dp3[i-1][j]

        if s[h-i-1][j] == "#":
            dp4[h-i-1][j] = 0
        elif h-i-1 == h-1:
            dp4[h-i-1][j] = 1
        else:
            dp4[h-i-1][j] = 1 + dp4[h-i][j]



        

a = 1
for i in range(h):
    for j in range(w):
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)


print(a)
### BUGGY CODE ###

K, S = [int(i) for i in input().split()]
pos = []
for a in range(K+1):
    for b in range(K+1):
        c = S - a - b
        if 0 <= c <= K:
            pos.append([a,b,c])
# for a in pos:
#     print(a)
print(len(pos))

### FIXED CODE ###

K, S = [int(i) for i in input().split()]
t = 0
for a in range(K+1):
    for b in range(a, K+1):
        c = S - a - b
        if 0 <= c <= K and c >= a and c >= b:
            if a == b == c:
                t += 1
            elif a == b or b == c:
                t += 3
            else:
                t += 6
print(t)
### BUGGY CODE ###

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

result = 1
for a in A:
  result *= a

if (result > 10 ** 18):
  print(-1)
else:
  print(result)

### FIXED CODE ###

import sys

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

if 0 in A:
    print(0)
    sys.exit()

result = 1
for a in list(A):
    result *= a
    if (result > 10 ** 18):
        print(-1)
        sys.exit()

print(result)
### BUGGY CODE ###

import sys
N,k=map(int,input().split())
A=[int(i) for i in input().split()]
if N==1:
    print(0)
    sys.exit()
dp=[0]*N
dp[0]=0
for i in range(1,N):
    j=1
    ans=float('inf')
    while True:
        if j<=k and i-j>=0:
            ans=min(abs(A[i]-A[i-j])+dp[i-j],ans)
            j+=1
        else:
            break
    dp[i]=ans
##print(dp)
    
print(dp[-1])
    
    


### FIXED CODE ###

import sys
N,k=map(int,input().split())
A=[int(i) for i in input().split()]
if N==1:
    print(0)
    sys.exit()
dp=[0]*N
dp[0]=0
for i in range(1,N):
    j=1
    ans=float('inf')
    while True:
        if j<=k and i-j>=0:
            ans=min(abs(A[i]-A[i-j])+dp[i-j],ans)
            j+=1
        else:
            break
    dp[i]=ans
##print(dp)
    
print(dp[-1])
### BUGGY CODE ###

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

s = ''

while (len(s) <= n):
    for i in range(a):
        s += 'b'
    for i in range(b):
        s += 'r'

tmp = s[0:n]

print(tmp.count('b'))


### FIXED CODE ###

n, a, b = map(int, input().split())
tmp = (n % (a+b))

if a == 0:
    print('0')
elif tmp == 0:
    print(a * (n // (a+b)))
else:
    if tmp < a:
        print(a * (n // (a+b)) + tmp)
    else:
        print(a * (n // (a+b)) + a)
### BUGGY CODE ###

import sys
import bisect
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

MOD = 10 ** 9 + 7

dp = [[0] * (M+1) for _ in range(N+1)]
dp_cum = [[0] * (M+1) for _ in range(N+1)]

for x in range(N):
    for y in range(M):
        if S[x] == T[y]:
            dp[x + 1][y + 1] += dp_cum[x][y] + 1
            dp[x + 1][y + 1] %= MOD

        dp_cum[x + 1][y + 1] = (dp_cum[x+1][y] % MOD) \
            + (dp_cum[x][y + 1] % MOD) \
            - (dp_cum[x][y] % MOD) \
            + (dp[x + 1][y + 1] % MOD)

        dp_cum[x + 1][y + 1] %= MOD

        #print("---x,y", x, y, "----")
        #print("dp:", dp)
        #print("dp_cum", dp_cum)


ans = dp_cum[N][M] + 1
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

MOD = 10 ** 9 + 7

dp = [[0] * (M+1) for _ in range(N+1)]
dp_cum = [[0] * (M+1) for _ in range(N+1)]

for x in range(N):
    for y in range(M):
        if S[x] == T[y]:
            dp[x + 1][y + 1] += dp_cum[x][y] + 1
            dp[x + 1][y + 1] %= MOD

        dp_cum[x + 1][y + 1] = (dp_cum[x+1][y] % MOD) \
            + (dp_cum[x][y + 1] % MOD) \
            - (dp_cum[x][y] % MOD) \
            + (dp[x + 1][y + 1] % MOD)

        dp_cum[x + 1][y + 1] %= MOD

        #print("---x,y", x, y, "----")
        #print("dp:", dp)
        #print("dp_cum", dp_cum)


ans = dp_cum[N][M] + 1
print(ans)
### BUGGY CODE ###

from itertools import product
from bisect import bisect_left
N,Ma,Mb = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
if N==1:
    if A[0][0]*Mb==A[0][1]*Ma:
        print(A[0][2])
    else:
        print(-1)
else:
    A1 = A[:N//2]  # N//2
    A2 = A[N//2:]  # N-N//2
    B1 = []
    for x in product((0,1),repeat=N//2):
        cnt1 = 0
        cnt2 = 0
        for i in range(N//2):
            if x[i]==1:
                cnt1 += Ma*A1[i][1]-Mb*A1[i][0]
                cnt2 += A1[i][2]
        B1.append((cnt1,cnt2))
    B2 = []
    for x in product((0,1),repeat=N-N//2):
        cnt1 = 0
        cnt2 = 0
        for i in range(N-N//2):
            if x[i]==1:
                cnt1 += Ma*A2[i][1]-Mb*A2[i][0]
                cnt2 += A2[i][2]
        B2.append((cnt1,cnt2))
    B1 = sorted(B1,key=lambda x:x[1])
    B1 = sorted(B1,key=lambda x:x[0])
    B2 = sorted(B2,key=lambda x:x[1])
    B2 = sorted(B2,key=lambda x:x[0])
    cmin = 10000
    for b1 in B1:
        b,c = b1[0],b1[1]
        if c==0:
            ind = bisect_left(B2,(-b,1))
        else:
            ind = bisect_left(B2,(-b,0))
        if ind<len(B2) and B2[ind][0]==-b:
            cmin = min(cmin,c+B2[ind][1])
    if cmin>=10000:
        print(-1)
    else:
        print(cmin)

### FIXED CODE ###

INFTY = 10**4
N,Ma,Mb = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
dp = [[[INFTY for _ in range(401)] for _ in range(401)] for _ in range(N+1)]
dp[0][0][0] = 0
for i in range(1,N+1):
    for j in range(401):
        for k in range(401):
            dp[i][j][k] = dp[i-1][j][k]
            a = A[i-1][0]
            b = A[i-1][1]
            c = A[i-1][2]
            if j>=a and k>=b:
                dp[i][j][k] = min(dp[i][j][k],dp[i-1][j-a][k-b]+c)
cmin = INFTY
for j in range(1,401):
    for k in range(1,401):
        if j*Mb==k*Ma:
            cmin = min(cmin,dp[N][j][k])
if cmin>=INFTY:
    print(-1)
else:
    print(cmin)