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

h, n = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(n)]
h_max = 10 ** 4
inf = 10 ** 9
dp = [inf] * (h_max + 1)
dp[0] = 0
for h_target in range(1, h_max + 1):
    for attack, mp in AB:
        h_remain = max(0, h_target - attack)
        dp[h_target] = min(dp[h_target], dp[h_remain] + mp)
print(dp[h])


### FIXED CODE ###

h, n = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(n)]
h_max = 10 ** 4
inf = 10 ** 9
dp = [inf] * (h_max + 1)
dp[0] = 0
for h_target in range(1, h_max + 1):
    for attack, mp in AB:
        h_remain = max(0, h_target - attack)
        dp[h_target] = min(dp[h_target], dp[h_remain] + mp)
print(dp[h])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(N):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
count = 0
ans = []
bfs(0,G,queue,dist)
for v in range(1,N): 
    for el in G[v]: 
        if dist[v] == dist[el] + 1:
            ans.append(el+1)
            count += 1
            break
if count == N-1:
  print("Yes")
  for el in ans:
    print(el)
else:
  print("No")
    


### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**9)
    from sys import stdin
    def input() : return stdin.readline().rstrip()
    N,M = map(int,input().split())
    dist = [-1] * N
    G = dict()
    for i in range(N):
        G[i] = []   
    for _ in range(M):
        a,b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    q = [0]
    pre = [0] * N
    dist[0] = 0
    while (q != []):
        v = q[0]
        q.remove(q[0])
        for vertex in G[v]:
            if dist[vertex] != -1:
                continue
            dist[vertex] = dist[v] + 1
            pre[vertex] = v
            q.append(vertex)
    print("Yes")
    for v in range(1,N): 
        print(pre[v]+1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import Counter

N=int(input())
A=[int(x) for x in input().split()]
A_s=list(dict.fromkeys(A))
Com=0

A_C=Counter(A)

for name,x in A_C.items():
    Com+=int(x*(x-1)/2)
    
for i in range(N):
    y=A.count(A[i])
    print(Com-y+1)

### FIXED CODE ###

from collections import Counter

N=int(input())
A=[int(x) for x in input().split()]
Com=0

A_C=Counter(A)

for name,x in A_C.items():
    Com+=int(x*(x-1)/2)
    
for i in range(N):
    y=A_C[A[i]]
    print(Com-y+1)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(1, N + 1):
    a = i * (N // i) * (N // i + 1) / 2
    A.append(round(a))
print(sum(A))

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N + 1):
    b = N // i
    ans += i * b * (b + 1) // 2
print(ans)
### BUGGY CODE ###

# 2019/12/27

import sys
input=sys.stdin.readline

h,w=map(int,input().split())
s=[list('#'*(w+2))]
for _ in range(h):
    s+=[list('#'+input()+'#')]
s+=[list('#'*(w+2))]

G=[]
for i in range(h+2):
    g=[]
    for j in range(w+2):
        g.append([0,0,0,0])
    G.append(g)
L,U,R,D=list(range(4))

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":continue
        G[i][j][L]=G[i][j-1][L]+1
        G[i][j][U]=G[i-1][j][U]+1
        
ans=0

for i in range(h,0,-1):
    for j in range(w,0,-1):
        if s[i][j]=="#":continue
        G[i][j][R]=G[i][j+1][R]+1
        G[i][j][D]=G[i+1][j][D]+1
        lit=sum(G[i][j])-3
        ans=max(ans,lit)
print(ans)

### FIXED CODE ###

# 2019/12/27

h,w=map(int,input().split())
s=[list('#'*(w+2))]
for _ in range(h):
    s+=[list('#'+input()+'#')]
s+=[list('#'*(w+2))]

L,U,R,D=[[[0]*(w+2) for _ in range(h+2)] for _ in range(4)]

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":continue
        L[i][j]=L[i][j-1]+1
        U[i][j]=U[i-1][j]+1

ans=0

for i in range(h,0,-1):
    for j in range(w,0,-1):
        if s[i][j]=="#":continue
        R[i][j]=R[i][j+1]+1
        D[i][j]=D[i+1][j]+1
        lit=L[i][j]+U[i][j]+R[i][j]+D[i][j]-3
        ans=max(ans,lit)
print(ans)
### BUGGY CODE ###

from collections import defaultdict
def main2():
    ketaone = [0]*61
    MOD = 10**9 + 7
    n = int(input())
    A=[int(i) for i in input().split()]

    for i in A:
        for j in range(61):
            if i&(1<<j):
                ketaone[j]+=1
    res = 0

    for i in range(61):
        res = res + (ketaone[i]*(n-ketaone[i])*(2**i))%MOD
        res%=MOD
    print(res)


def main1():
    n = int(input())
    lis = [[] for _ in range(n)]
    for i in range(n):
        a = int(input())
        for j in range(a):
            lis[i].append(list(map(int, input().split())))
    res = 0

    for i in range(1<<n):
        f = True
        uso=set()
        syo=set()
        tmp=0
        for j in range(n):
            if(i&(1<<j)):
                tmp+=1
                for k in lis[j]:
                    if (i&(1<<(k[0]-1))) and k[1]==0:
                        f=False
                    if k[1]==1 and not (i&(1<<k[0]-1)):
                        f=False
        if f:
            res = max(res,tmp)
    print(res)


if __name__ == '__main__':
    main2()


### FIXED CODE ###

def main():
    n = int(input())
    A=[int(i) for i in input().split()]
    MOD = 10**9 + 7
    t = 0
    k = max(A)
    while k>0:
        k=k//2
        t+=1

    bisu = [0]*(t+1)
    zerobi = [0]*(t+1)
    res = 0
    for i in range(n):
        for j in range(t+1):
            if A[i]&(1<<j):
                bisu[j]+=1

    for i in range(t+1):
        res = res + (bisu[i]*(n-bisu[i])*(2**i))%MOD
    print(res%MOD)

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

def cal_factors(num):
    factors = {}
    mod = 2
    while num >= 2:
        if num % mod == 0:
            if mod in factors:
                factors[mod] += 1
            else:
                factors[mod] = 1
            num //= mod
        else:
            mod += 1

    return factors


def comb(n, r, mod):
    result = 1
    r = min(r, n-r)
    for i in range(n, n-r, -1):
        result *= i
    for i in range(2, r+1):
        result //= i
    result %= mod

    return result


n, m = [int(v) for v in input().split()]

mod = 1000000000 + 7
factors = cal_factors(m)
ans = 1
for v in factors.values():
    ans *= comb(v + n - 1, v, mod)
    ans %= mod

print(ans)

### FIXED CODE ###

from math import sqrt

def cal_factors(num):
    factors = {}
    i = 0
    while True:
        d, q = divmod(num, 2)
        if q == 0:
            num = d
            i += 1
            factors[2] = i
        else:
            break

    maxmod = int(sqrt(num)) + 1
    for mod in range(3, maxmod, 2):
        i = 0
        while True:
            d, q = divmod(num, mod)
            if q == 0:
                num = d
                i += 1
                factors[mod] = i
            else:
                break

    if num > 1:
        factors[num] = 1

    return factors


def comb(n, r, mod):
    result = 1
    r = min(r, n-r)
    for i in range(n, n-r, -1):
        result *= i
    for i in range(2, r+1):
        result //= i
    result %= mod

    return result


n, m = [int(v) for v in input().split()]

mod = 1000000000 + 7
factors = cal_factors(m)
ans = 1
for v in factors.values():
    ans *= comb(v + n - 1, v, mod)
    ans %= mod

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

n,c = map(int,input().split())
d = [list(map(int,input().split())) for i in range(c)]
g = [list(map(int,input().split())) for i in range(n)]
# mod=0,1,2について、色iに変えた時のコストをまとめておく
cost = [[0]*c for i in range(3)]
for i in range(3):
    for j in range(c):
        cost[i][j] = sum([d[g[a][b]-1][j] for a in range(n) for b in range(n) if (a+b)%3==i])
# mod=0,1,2について、どの色で塗るか全探索
ret=10**10
for i in range(c):
    for j in range(c):
        for k in range(c):
            if i==j or j==k or k==i:
                continue
            ret=min(ret, cost[0][i]+cost[1][j]+cost[2][k])
print(ret)

### FIXED CODE ###

n,c = map(int,input().split())
d = [list(map(int,input().split())) for i in range(c)]
g = [list(map(int,input().split())) for i in range(n)]
# mod=0,1,2について、色iに変えた時のコストをまとめておく
cost = [[0]*c for i in range(3)]
for i in range(3):
    for j in range(c):
        for a in range(n):
            for b in range(n):
                if (a+b)%3==i:
                    cost[i][j]+=d[g[a][b]-1][j]
# mod=0,1,2について、どの色で塗るか全探索
ret=10**10
for i in range(c):
    for j in range(c):
        for k in range(c):
            if i==j or j==k or k==i:
                continue
            ret=min(ret, cost[0][i]+cost[1][j]+cost[2][k])
print(ret)
### BUGGY CODE ###

from sys import stdin
import itertools

l,r = [int(x) for x in stdin.readline().rstrip().split()]


li = [x for x in range(l,r+1)]
m = 2020
for i in range(len(li)-1):
    for j in range(i+1,len(li)):
        if li[i]*li[j]%2019 == 0:
            print(0)
            exit()
        else:
            if m >= li[i]*li[j]%2019:
                m = li[i]*li[j]%2019
print(m)

### FIXED CODE ###

from sys import stdin

l,r = [int(x) for x in stdin.readline().rstrip().split()]
m = 2020
if r - l > 2018:
    print(0)
    exit()
for i in range(l,r):
    for j in range(i+1,r+1):
        if i*j%2019 == 0:
            print(0)
            exit()
        else:
            m = min(m,i*j%2019)
print(m)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n, k = MAP()
    p = LIST()

    ans = 0
    tmp = 0

    for i in range(n-k+1):
        if tmp < sum(p[i:i+k]):
            l = p[i:i+k]
            tmp = sum(p[i:i+k])

    #print(l)
    k = list(accumulate(range(max(l)+1)))

    for x in l:
        ans += k[x]/x
        
    print(ans)

if __name__=='__main__':
    main()


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n, k = MAP()
    p = LIST()
    ans = 0
    tmp = 0
    if n == k:
        k = list(accumulate(range(max(p)+1)))
        for x in p:
            ans += k[x]/x
        
        print(ans)
        sys.exit()

    p_ = list(accumulate(p))
    #print(p_)


    for i in range(n-k):
        #print(i,p_[i+k]-p_[i])
        if tmp <= p_[i+k]-p_[i]:
            l = p[i+1:i+k+1]
            tmp = p_[i+k]-p_[i]

    #print('l:',l)
    k = list(accumulate(range(max(l)+1)))

    for x in l:
        ans += k[x]/x
        
    print(ans)

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

S = input()
N = len(S)
for _ in range(N//2):
    S = S.replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','')

    if S.count('01') == 0 and S.count('10') == 0:
        break
print(N - len(S))

### FIXED CODE ###

S = input()
r = S.count('0')
b = S.count('1')
print(min(r,b)*2)
### BUGGY CODE ###

N = int(input())
SS = []
G1,G2,G3,G4 = [],[],[],[]
cnt2 = 0
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        cnt2 += cnt
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        G3.append([MIN,cnt])
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])


G2.sort(reverse=True)
for L in G2:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]
G4.sort()
for L in G4:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]

cnt2 += sum(L[1] for L in G3)

if cnt2 == 0:
    print('Yes')
else:
    print('No')



### FIXED CODE ###

N = int(input())
G2,G4 = [],[]
cnt2 = 0
cnt3 = 0
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        cnt2 += cnt
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        cnt3 += cnt
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])


G2.sort(reverse=True)
for L in G2:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]
for L in G4:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]

cnt2 += cnt3

if cnt2 == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

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

dummy=set()
loop=[]
X=set(range(N))
while len(dummy)!=N:
  a=[]
  k=min(X-dummy)
  a.append(k)
  dummy.add(k)
  l=P[k]-1
  while l!=k:
    a.append(l)
    dummy.add(l)
    l=P[l]-1
  loop.append(a)

ans=-(10**300)
for l in loop:
  temp=0
  s=len(l)
  ssum=0
  k=0
  for i in range(s):
    ssum+=C[l[i]]
  if ssum>0:
    temp+=((K-1)//s)*ssum
    k=K-((K-1)//s)*s
  else:
    k=min(K,s)
  kmax=-(10**300)
  for ii in range(1,k+1):
    for jj in range(s):
      tempscore=temp
      for kk in range(ii):
        tempscore+=C[l[(jj+kk)%s]]
      if tempscore>kmax:
        kmax=tempscore
  if kmax>ans:
    ans=kmax
print(ans)


### FIXED CODE ###

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

dummy=set()
loop=[]
X=set(range(N))
while len(dummy)!=N:
  a=[]
  k=min(X-dummy)
  a.append(k)
  dummy.add(k)
  l=P[k]-1
  while l!=k:
    a.append(l)
    dummy.add(l)
    l=P[l]-1
  loop.append(a)

ans=-(10**300)
for l in loop:
  temp=0
  s=len(l)
  ssum=0
  k=0
  for i in range(s):
    ssum+=C[l[i]]
  if ssum>0:
    temp+=((K-1)//s)*ssum
    k=K-((K-1)//s)*s
  else:
    k=min(K,s)
  kmax=-(10**300)
  for ii in range(s):
    tempscore=temp
    for jj in range(1,k+1):
      tempscore+=C[l[(ii+jj)%s]]
      if tempscore>kmax:
        kmax=tempscore
  if kmax>ans:
    ans=kmax
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]

for i in range(n):
    ans = 0
    for j in range(n):
        if j == i:
            continue
        
        ans = ans^a[j]
        
    print(ans, end=' ')


### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

ans = 0
for i in range(n):
    ans = ans^a[i]
    
for i in range(n):
    print(ans^a[i], end=' ')
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
 
if 0 in A:
  print(0)
else:
  ans = 1
  for i in range(N):
    ans *= A[i]
  if ans > 10**18:
    print(-1)
  else:
    print(ans)

### FIXED CODE ###

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

limit = 10 ** 18
A.sort()
result = A[0]
for a in A[1:]:
    result *= a
    if result > limit:
        print(-1)
        exit()
print(result)
### BUGGY CODE ###

n=int(input())
aa=list(map(int,input().split()))
aa.append(0)
aaa=tuple(aa)
a=list(aaa)
x=[0]*(n+1)
for i in range(n-1):
    if a[i]<0:
        a[i]=-1*a[i]
        a[i+1]=-1*a[i+1]
        x[i+1]=max(sum(a),x[i])


print(max(max(x),sum(aa)))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
c=0
for i in range(n):
    if a[i]<0:
        c+=1
        a[i]=-1*a[i]
aa=list(map(abs,a))
if c%2==0:
    print(sum(aa))
else:
    print(sum(aa)-2*min(aa))
### BUGGY CODE ###

N = int(input())
i = 1
for n in range(N):
    i = i*(n+1)
print(i%(10**9+7))

### FIXED CODE ###

N = int(input())
i = 1
for n in range(N):
    i = i*(n+1)%(10**9+7)
print(i)
### BUGGY CODE ###

n, q = map(int, input().split())
link = dict()
counter = list([0]*n)
for i in range(n-1):
  a, b = map(int, input().split())
  link[b-1] = a-1
        
for i in range(q):
  p,pp = map(int, input().split())
  counter[p-1] += pp
ans = ""
for i in range(n):
    isChild = True
    now = i
    count = counter[now]
    while True:
        if now in link:
            count += counter[link[now]]
            now = link[now]
        else:
            break
    
    if i != n-1:
        ans += str(count) + " "
    else: ans += str(count)
print(ans)
  

### FIXED CODE ###

n, q = map(int, input().split())
link = dict()
counter = list([0]*n)
for i in range(n-1):
    a,b = map(int, input().split())
    link[b-1] = a-1
        
for i in range(q):
  p,pp = map(int, input().split())
  counter[p-1] += pp

for i in range(n):
    if i in link:
        counter[i] += counter[link[i]]

counter = map(str, counter)
ans = " ".join(counter)
print(ans)
### BUGGY CODE ###

N = int(input())
L = sorted([int(i) for i in input().split()])
count = 0

from bisect import bisect_left as bi

for j in range(N):
    for k in range(j + 1,N - 1):
        right = L[j] + L[k]
        left = abs(L[j] - L[k])
        L_slice = L[k:N]
        ite_right = bi(L_slice,right)
        count = count + (ite_right - 1)

print(count) 

### FIXED CODE ###

N = int(input())
L = sorted([int(i) for i in input().split()])
count = 0

from bisect import bisect_left as bi

for j in range(N):
    for k in range(j + 1,N - 1):
        right = L[j] + L[k]
        ite_right = bi(L,right)
        count = count + (ite_right - k - 1)

print(count)
### BUGGY CODE ###

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

ninoshima=[]
for i in range(m):
    if ab[i][0]==1:
        ninoshima.append(ab[i][1])

for i in range(m):
    if ab[i][0] in ninoshima and ab[i][1]==n:
        print("POSSIBLE")
        quit()
    elif ab[i][1] in ninoshima and ab[i][0]==n:
        print("POSSIBLE")
        quit()

print("IMPOSSIBLE")

### FIXED CODE ###

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

ninoshima=[[0]*(n+1) for i in range(2)]

for i in range(m):
    if ab[i][0]==1:
        ninoshima[0][ab[i][1]]=1
    if ab[i][1]==n:
        ninoshima[1][ab[i][0]]=1
    

for i in range(n+1):
    if ninoshima[0][i]==ninoshima[1][i]==1:
        print("POSSIBLE")
        quit()

print("IMPOSSIBLE")
### BUGGY CODE ###

n,ma,mb = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(n)]
dp = [[[float("inf") for i in range(10*n+1)] for i in range(10*n+1)] for i in range(n+1)]
dp[0][0][0],ans = 0,float("inf")
for i in range(1,n+1):
	for j in range(10*(i-1)+1):
		for k in range(10*(i-1)+1):
			dp[i][j][k] = min(dp[i-1][j][k],dp[i][j][k])
			dp[i][j+x[i-1][0]][k+x[i-1][1]] = min(dp[i][j+x[i-1][0]][k+x[i-1][1]],dp[i-1][j][k]+x[i-1][2])
for i in range(1,10*n+1):
	for j in range(1,10*n+1):
		if i*mb==j*ma: ans = min(ans,dp[n][i][j])
if ans==float("inf"): print(-1)
else: print(ans)

### FIXED CODE ###

n, ma, mb = map(int, input().split())
INF = float("inf")
dp = [[[INF for i in range(10*n+1)] for i in range(10*n+1)] for i in range(n+1)]
dp[0][0][0],ans = 0,INF
for i in range(1,n+1):
    a,b,c = (int(l) for l in input().split())
    for j in range(10*(i-1)+1):
        for k in range(10*(i-1)+1):
            if dp[i-1][j][k] != INF:
              dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k])
              dp[i][j+a][k+b] = min(dp[i][j+a][k+b], dp[i-1][j][k]+c)
for i in range(ma,10*n+1,ma):
	if i*mb//ma<=10*n: ans=min(ans,dp[n][i][i*mb//ma])
if ans==INF: print(-1)
else: print(ans)
### BUGGY CODE ###

H,W,D = map(int,input().split())
A = {}
for i in range(H):
    l = list(map(int,input().split()))
    for j in range(W):
        A[l[j]] = [i+1,j+1]

Q = int(input())
LR = []
for i in range(Q):
    LR.append(list(map(int,input().split())))


ru = {}
for i in range(1,H*W+1):
    if i not in ru.keys():
        ru[i] = [0]
        c = 1
    while i + D*c <= H*W:
        now = A[i+D*(c-1)]
        will = A[i+D*c]
        mp = abs(will[0] - now[0]) + abs(will[1] - now[1])
        ru[i].append(mp + ru[i][c-1])
        c += 1




for i in range(Q):
    print(ru[LR[i][0]][(LR[i][1] - LR[i][0]) // D])


### FIXED CODE ###

H,W,D = map(int,input().split())
A = {}
for i in range(H):
    l = list(map(int,input().split()))
    for j in range(W):
        A[l[j]] = [i+1,j+1]

Q = int(input())
LR = []
for i in range(Q):
    LR.append(list(map(int,input().split())))


ru = {}
for i in range(1,D+1):
    ru[i] = [0]

for i in range(1,D+1):
    c = 1
    while i + D*c <= H*W:
        now = A[i+D*(c-1)]
        will = A[i+D*c]
        mp = abs(will[0] - now[0]) + abs(will[1] - now[1])
        ru[i].append(mp + ru[i][c-1])
        c += 1

for i in range(Q):
    t = LR[i][0] % D
    if t == 0:
        t = D
        print(ru[t][LR[i][1]//D-1] - ru[t][LR[i][0]//D-1])
    else:
        print(ru[t][LR[i][1]//D] - ru[t][LR[i][0]//D])
### BUGGY CODE ###

def main():

    div = 1000000007

    n, m = map(int, input().split())
    a = [int(input()) for i in range(m)]

    f = [0] * (n + 1)
    f[0] = 1

    if 1 not in a:
        f[1] = 1

    for i in range(2, n + 1):
        if i in a:
            continue
        f[i] = (f[i - 1] + f[i - 2]) % div

    print(f[-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, M, *a = map(int, open(0).read().split())
    div = 1000000007
    broken = set(a)
 
    comb_list = [0] * (N + 1)
    comb_list[0] = 1
    if 1 not in broken:
        comb_list[1] = 1
 
    for i in range(2, N + 1):
        if i in broken:
            continue
        comb_list[i] = (comb_list[i - 1] + comb_list[i - 2]) % div
 
    print(comb_list[-1])
 
 
if __name__ == "__main__":
    main()