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

def main():
    h, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    dp = [10**10]*(h+1)
    dp[0] = 0
    for i in range(h):
        p = dp[i]
        for a, b in ab:
            j = i+a
            if j > h:
                j = h
            dp[j] = min(dp[j], p+b)
    print(dp[-1])


main()

### FIXED CODE ###

def main():
    h, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    dp = [10**10]*(h+1)
    dp[0] = 0
    for i in range(h):
        for a, b in ab:
            j = i+a
            if j > h:
                j = h
            dp[j] = min(dp[j], dp[i]+b)
    print(dp[-1])


main()
### BUGGY CODE ###

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

c=1
path=[]
d={}
l=0
while l<=k:
    if c in path:
        p=d[c]
        #print(p, path)
        pattern_l = l-p
        k-=((k-p)//pattern_l)*pattern_l
    path.append(c)
    l+=1
    d[c]=l-1
    c=A[c-1]
print(path[k])


### FIXED CODE ###

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

c=1
path=[]
d={}
l=0
while l<=k:
    if c in d:
        p=d[c]
        #print(p, path)
        pattern_l = l-p
        k-=((k-p)//pattern_l)*pattern_l
    path.append(c)
    l+=1
    d[c]=l-1
    c=A[c-1]
print(path[k])
### BUGGY CODE ###

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

hako = [0 for i in range(N)]

for i in A:
    hako[i-1] += 1

for i in range(N):
    sum = 0
    tmp = A[i] - 1
    hako[tmp] -= 1

    for j in hako:
        if j > 1:
            sum += math.factorial(j) // (math.factorial(j - 2) * math.factorial(2))
    
    print(sum)

    hako[tmp] += 1

### FIXED CODE ###

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

hako = [0 for i in range(N)]
sum = 0

c = collections.Counter(A)

for v in c.values():
    sum += int(v * (v-1) / 2)


for k in range(N):
    print(sum-(c[A[k]] - 1))
### BUGGY CODE ###

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

l = [[0] * w for _ in range(h)]
r = [[0] * w for _ in range(h)]
u = [[0] * w for _ in range(h)]
d = [[0] * w for _ in range(h)]

for i in range(h):
  for j in range(w):
    if s[i][j] == '.':
      if j == 0:
        l[i][j] = 1
      else:
        l[i][j] = l[i][j-1] + 1
    if s[i][w-j-1] == '.':
      if j == 0:
        r[i][w-j-1] = 1
      else:
        r[i][w-j-1] = r[i][w-j] + 1

for j in range(w):
  for i in range(h):
    if s[i][j] == '.':
      if i == 0:
        u[i][j] = 1
      else:
        u[i][j] = u[i-1][j] + 1
    if s[h-i-1][j] == '.':
      if i == 0:
        d[h-i-1][j] = 1
      else:
        d[h-i-1][j] = d[h-i][j] + 1

maximum = 1
for i in range(h):
  for j in range(w):
    maximum = max(maximum, l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3)
print(maximum)

### FIXED CODE ###

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

l = [[0] * w for _ in range(h)]
r = [[0] * w for _ in range(h)]
u = [[0] * w for _ in range(h)]
d = [[0] * w for _ in range(h)]

for i in range(h):
  for j in range(w):
    if s[i][j] == '.':
      if j == 0:
        l[i][j] = 1
      else:
        l[i][j] = l[i][j-1] + 1
    if s[i][w-j-1] == '.':
      if j == 0:
        r[i][w-j-1] = 1
      else:
        r[i][w-j-1] = r[i][w-j] + 1

for j in range(w):
  for i in range(h):
    if s[i][j] == '.':
      if i == 0:
        u[i][j] = 1
      else:
        u[i][j] = u[i-1][j] + 1
    if s[h-i-1][j] == '.':
      if i == 0:
        d[h-i-1][j] = 1
      else:
        d[h-i-1][j] = d[h-i][j] + 1

maximum = 1
for i in range(h):
  for j in range(w):
    maximum = max(maximum, l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3)
print(maximum)
### BUGGY CODE ###

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


### FIXED CODE ###

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

from collections import defaultdict
s=input()
n=len(s)
N=defaultdict(int)
x=0
for i in reversed(range(n)):
    x+=int(s[i])*(10**(n-i-1))
    x%=2019
    N[x%2019]+=1
ans=N[0]
for j in N.values():
    ans+=j*(j-1)//2
print(ans)

### FIXED CODE ###

from collections import defaultdict
s=input()
n=len(s)
N=defaultdict(int)
x=0
for i in reversed(range(n)):
    x+=int(s[i])*pow(10,(n-i-1),2019)
    x%=2019
    N[x]+=1
ans=N[0]
for j in N.values():
    ans+=j*(j-1)//2
print(ans)
### BUGGY CODE ###

s = list(input())
q = int(input())
lines = [list(input().split()) for i in range(q)]
 
def q1(s):
    for i in range(len(s) // 2):
        s[i],s[-1-i] = s[-1-i],s[i]
    return s
 
def q2(s, l):
    if int(l[1]) == 1:
        s.insert(0,l[2])
    else:
        s.extend(l[2])
    return s
 
for l in lines:
    if int(len(l)) == 1:
        q1(s)
    else:
        q2(s, l)
 
print(*s, sep='')

### FIXED CODE ###

from collections import deque

def check(reverse_cnt, t):

    if reverse_cnt%2 == 0 and t == 1:
        return True
    elif reverse_cnt%2 == 0 and t == 2:
        return False
    elif reverse_cnt%2 == 1 and t == 1:
        return False
    elif reverse_cnt%2 == 1 and t == 2:
        return True

def solve(s, q, qs):
    reverse_cnt = 0

    for item in qs:

        if len(item) == 1:
            # T = 1 文字列を反転
            reverse_cnt += 1
        else:
            # T = 2

            if check(reverse_cnt, int(item[1])):
                # 先頭に追加
                s.appendleft(item[2])

            else:
                # 末尾に追加
                s.append(item[2])


    if reverse_cnt%2 == 1:
        ans = "".join(s)
        ans = ans[::-1]
    else:
        ans = "".join(s)

    return ans

if __name__ == '__main__':

    s = deque() # queue

    str = input()
    q = int(input())
    qs = [list(input().split()) for i in range(q)]

    s.append(str)

    ans = solve(s, q, qs)
    print(ans)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
l=[list(map(int,input().split())) for _ in range(Q)]
for lz in l:
  print(S[lz[0]-1:lz[1]].count('AC'))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
k = [0] * (N+1)

for i in range(1,N):
  v = 1 if S[i-1]+S[i] == 'AC' else 0
  k[i] = k[i-1] + v
k[-1]=k[-2]
for _ in range(Q):
  f,l = map(int,input().split())
  print(k[l-1] - k[f-1])
### BUGGY CODE ###

N = int(input())
T = [[]for i in range(N)]
A = []
D = [[0]*N for i in range(N)]
for i in range(N-1):
    a,b = map(lambda x:int(x)-1,input().split())
    T[a].append(b)
    T[b].append(a)
    A.append((a,b))
K = 0
for t in T:
    K = max(K,len(t))
print(K)
Q = [(0,-1,0)]
while Q:
    q = Q.pop(-1)
    v,p,k = q[0],q[1],q[2]
    ck = 1
    for c in T[v]:
        if ck==k:ck+=1
        if c!=p:
            if len(T[c])!=1:
                Q.append((c,v,ck))
            D[c][v] = ck
            D[v][c] = ck
            ck+=1
for a in A:
    print(D[a[0]][a[1]])

### FIXED CODE ###

from collections import deque
N = int(input())
ab = [list(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
T = [[] for i in range(N)]
for a,b in ab:
    T[a].append(b)
q = deque([0])
color = [0]*N
while q:
    x = q.popleft()
    c = 1
    for y in T[x]:
        if c==color[x]:
            c+=1
        color[y] = c
        c+=1
        q.append(y)
print(max(color))
for i in range(N-1):
    print(color[ab[i][1]])
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

A = int(readline())
B = int(readline())

def can_make(A,B):
    # [A,B] の元のorで、{B} 以外の方法でBを作れるかどうか。たいていTrue
    if A == B:
        return False
    if B%2 == 0:
        return can_make((A+1)//2,B//2)
    # Bが奇数なら、{B-1,B}が満たす
    return True

def F(A,B):
    if A==B:
        return 1
    # 偶数の作り方
    ev = F((A+1)//2,B//2)
    # 奇数の作り方
    if A%2==0:
        A += 1
    if B%2 == 1:
        od = F(A//2,B//2)
    else:
        # 上位の桁では基本的にはA//2～B//2が使える。
        # ただし、{B} 以外でないといけない
        od = F(A//2,B//2)
        if not can_make(A//2,B//2):
            od -= 1
    return ev + od

answer = F(A,B)
print(answer)

### FIXED CODE ###

import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from functools import lru_cache

A = int(readline())
B = int(readline())

@lru_cache(None)
def can_make(A,B):
    # [A,B] の元のorで、{B} 以外の方法でBを作れるかどうか。たいていTrue
    if A == B:
        return False
    if B%2 == 0:
        return can_make((A+1)//2,B//2)
    # Bが奇数なら、{B-1,B}が満たす
    return True

@lru_cache(None)
def F(A,B):
    if A==B:
        return 1
    # 偶数の作り方
    ev = F((A+1)//2,B//2)
    # 奇数の作り方
    if A%2==0:
        A += 1
    if B%2 == 1:
        od = F(A//2,B//2)
    else:
        # 上位の桁では基本的にはA//2～B//2が使える。
        # ただし、{B} 以外でないといけない
        od = F(A//2,B//2)
        if not can_make(A//2,B//2):
            od -= 1
    return ev + od

answer = F(A,B)
print(answer)
### BUGGY CODE ###

import copy as c
n = int(input())
a = []
for i in range(n):
	a.append(int(input()))
maxs = []
for i in range(n):
	a2 = c.copy(a)
	a2[i] = 0
	maxs.append(max(a2))

for i in range(n):
	print(maxs[i])

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
	a.append(int(input()))
max1 = max(a)
idx = a.index(max1)
a[idx] = 0
max2 = max(a)

for i in range(n):
	if i != idx:
		print(max1)
	else:
		print(max2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    H, W, D = map(int, input().split())
    hw = [None for i in range(H*W+1)]

    for i in range(H):
        a = list(map(int, input().split()))
        for j in range(W):
            hw[a[j]] = [i, j]
    
    Q = int(input())

    # mem = [[None for i in range(W)] for i in range(H)]

    for i in range(Q):
        l, r = map(int, input().split())
        # if mem[l][r] != None:
        #     print(mem[l][r])
        # else:
        ans = 0
        for t in range(l, r, D):
            ans += abs(hw[t][0] - hw[t+D][0]) + abs(hw[t][1] - hw[t+D][1])
        print(ans)
        # mem[l][r]

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    H, W, D = map(int, input().split())
    hw = [None for i in range(H*W+1)]

    # 各数字の座標をhw[]に格納
    for i in range(H):
        a = list(map(int, input().split()))
        for j in range(W):
            hw[a[j]] = [i, j]

    # for i in range(len(hw)):
    #     print(i, hw[i])
    
    # Dのmodごとにmod Dからの距離を計算(累積和)
    modd = [0] * (H*W + 1)
    for start in range(D):
        tmp = start + D
        cost = 0
        if tmp == D:
            tmp = D * 2
        while tmp <= (H*W):
            tmp_cost = abs(hw[tmp][0] - hw[tmp-D][0]) + abs(hw[tmp][1] - hw[tmp-D][1])
            # print("{} - {} : {}".format(tmp-D, tmp, tmp_cost))
            # print(hw[tmp-D], hw[tmp], abs(hw[tmp][0] - hw[tmp-D][0]) + abs(hw[tmp][1] - hw[tmp-D][1]))
            cost += tmp_cost
            modd[tmp] = cost
            tmp += D
    # print(modd)
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        print(modd[r] - modd[l])

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

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

  ans = 0
  if P == 2 or P == 5:
    for i in range(N):
      if int(S[i])%P == 0:
        ans += i+1
  else:
    r = [0] * (N+1)
    for i in range(N):
      r[N-1-i] = int(S[N-1-i:])%P
    # for i in range(N):
    #   for j in range(i,N):
    #     if (r[i]-r[j+1])%P == 0:
    #       ans += 1
    d = {}
    for x in r:
      if x in d:
        d[x] += 1
      else:
        d[x] = 1
    for k,v in d.items():
      ans += v*(v-1)//2
  
  print(ans)

if __name__ == '__main__':
  main()

### FIXED CODE ###

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

  ans = 0
  if P == 2 or P == 5:
    for i in range(N):
      if int(S[i])%P == 0:
        ans += i+1
  else:
    # r = [0] * (N+1)
    # for i in range(N):
    #   r[N-1-i] = int(S[N-1-i:])%P
    # for i in range(N):
    #   for j in range(i,N):
    #     if (r[i]-r[j+1])%P == 0:
    #       ans += 1
    d = {}
    r = 0
    for i in range(N):
      r = (r+int(S[N-1-i])*pow(10,i,P))%P
      if r in d:
        d[r] += 1
      else:
        d[r] = 1
    if 0 in d:
      d[0] += 1
    for k,v in d.items():
      ans += v*(v-1)//2
  
  print(ans)

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

N, W = map(int, input().split())
w = [0]*N
v = [0]*N

for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0]*(W+1) for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j >= w[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
w = [0]*N
v = [0]*N

for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0]*(W+1) for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j >= w[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)
N, Q = map(int, input().split())

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

operations = [0] * N
for i in range(Q):
    p,q =  map(int, input().split())
    operations[p-1] += q

ans = [0] * N

def func(node,p_node):
    ans[node-1] += operations[node-1]
    if p_node != 0:
        connection[node-1].remove(p_node)
    for c_node in connection[node-1]:
        ans[c_node-1] += ans[node-1]
        func(c_node, node)

func(1, 0)

print(' '.join(map(str, ans)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)
from collections import deque

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

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

operations = [0] * N
for i in range(Q):
    p,q =  map(int, input().split())
    operations[p-1] += q

ans = [0] * N

stack = deque([1])
while len(stack)>0:
    node = stack.pop()
    ans[node-1] += operations[node-1]
    for node_c in connection[node-1]:
        connection[node_c-1].remove(node)
        ans[node_c-1] += ans[node-1]
        stack.append(node_c)

print(' '.join(map(str, ans)))
### BUGGY CODE ###

import re
S = input()
#print(type(S))

s = []
for i in range(int(S) // 2019):
    s.append(str(i*2019))

count = 0
for i in s:
    S_ = S
    while re.search(i, S_):
        #print(i)
        S_ = S_[:re.search(i, S_).start()] + "," + S_[re.search(i, S_).start()+1:]
        count += 1
        
print(count)

### FIXED CODE ###

S = input()

n = len(S)
m = 2019

S_ = S[::-1]

x = 1
total = 0
modlis = [0 for i in range(m)]

ans = 0
for i in range(n):
    modlis[total] += 1
    #print("S_[i]:", S_[i])
    #print("int(S_[i])*x:", int(S_[i])*x)
    #print("total:", total)
    total += int(S_[i])*x
    #print("total:", total)
    total %= m
    #print("total:", total)
    ans += modlis[total]
    #print("x:", x)
    x = x * 10 % m
    #print("x:", x)

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

N,M,Q=map(int,input().split())
N=800
A=[]
for i in range(M+Q):
    L,R=map(int,input().split())
    A.append([L,R])
#print(A)
B = [[0 for i in range(N+1)] for j in range(N+1)]

for i in range(M):
    B[A[i][0]][A[i][1]] +=1
#print(*B,sep='\n')
C = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N):
    for k in range(N):
        if k==0:
            C[i][k] = B[i][k]
        else:
            C[i][k] += C[i][k-1]+B[i][k]
#print('\n')
#print(*C,sep='\n')
for i in range(M,M+Q):
    total=0
    for k in range(N):
        if A[i][0]<=k<=A[i][1]:
            total+=C[k][A[i][1]]-C[k][A[i][0]-1]
    print(total)

### FIXED CODE ###

N,M,Q=map(int,input().split())
N=550
A=[]
for i in range(M+Q):
    L,R=map(int,input().split())
    A.append([L,R])
#print(A)
B = [[0 for i in range(N+1)] for j in range(N+1)]

for i in range(M):
    B[A[i][0]][A[i][1]] +=1
#print(*B,sep='\n')
C = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N):
    for k in range(N):
        if k==0:
            C[i][k] = B[i][k]
        else:
            C[i][k] += C[i][k-1]+B[i][k]
#print('\n')
#print(*C,sep='\n')
for i in range(M,M+Q):
    total=0
    for k in range(N):
        if A[i][0]<=k<=A[i][1]:
            total+=C[k][A[i][1]]-C[k][A[i][0]-1]
    print(total)
### BUGGY CODE ###

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

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

A_max = max(A)
prime = [[] for _ in range(A_max + 1)]
for i in range(2,A_max + 1):
    if prime[i] == []:
        n = i
        while n <= A_max:
            prime[n].append(i)
            n += i

li = [0] * (A_max + 1)
for a in A:
    for p in prime[a]:
        li[p] += 1


if max(li) <= 1:
    print('pairwise coprime')
elif max(li) == N:
    print('not coprime')
else:
    print('setwise coprime')

### FIXED CODE ###

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

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

A_max = max(A)
prime = [[] for _ in range(A_max + 1)]
for i in range(2,A_max + 1):
    if prime[i] == []:
        n = i
        while n <= A_max:
            prime[n].append(i)
            n += i

li = [0] * (A_max + 1)
for a in A:
    for p in prime[a]:
        li[p] += 1


if max(li) <= 1:
    print('pairwise coprime')
elif max(li) == N:
    print('not coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

import math
k=int(input())
ans=0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans+=math.gcd(math.gcd(a,b),c)
print(ans)

### FIXED CODE ###

import math
k=int(input())
ans=0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans+=math.gcd(math.gcd(a,b),c)
print(ans)
### BUGGY CODE ###

#input
N = int(input())
S = str(input())

#output
from collections import Counter
answer = 0
if N > 3:
    for i in range(N-2):
        for j in range(i+1, N-1):
            k = 2*j-i
            if S[i] == "R":
                if S[j] == "G":
                    answer += Counter(S[j+1:])["B"]
                    if k < N:
                        if S[k] == "B":
                            answer -= 1
                elif S[j] == "B":
                    answer += Counter(S[j+1:])["G"]
                    if k < N:
                        if S[k] == "G":
                            answer -= 1
            elif S[i] == "G":
                if S[j] == "R":
                    answer += Counter(S[j+1:])["B"]
                    if k < N:
                        if S[k] == "B":
                            answer -= 1
                elif S[j] == "B":
                    answer += Counter(S[j+1:])["R"]
                    if k < N:
                        if S[k] == "R":
                            answer -= 1
            elif S[i] == "B":
                if S[j] == "R":
                    answer += Counter(S[j+1:])["G"]
                    if k < N:
                        if S[k] == "G":
                            answer -= 1
                elif S[j] == "G":
                    answer += Counter(S[j+1:])["R"]
                    if k < N:
                        if S[k] == "R":
                            answer -= 1
                
print(answer)

### FIXED CODE ###

#input
N = int(input())
S = str(input())

#output
from collections import Counter
answer = 0
if N > 3:
    for i in range(1, N-1):
        if S[i] == "R":
            a = Counter(S[:i])["G"]
            b = Counter(S[i+1:])["B"]
            c = Counter(S[:i])["B"]
            d = Counter(S[i+1:])["G"]
            answer += a*b + c*d
            for j in range(1, min(i+1, N-i)):
                if S[i-j] != "R" and S[i+j] != "R" and S[i-j] != S[i+j]:
                    answer -= 1
        elif S[i] == "B":
            a = Counter(S[:i])["R"]
            b = Counter(S[i+1:])["G"]
            c = Counter(S[:i])["G"]
            d = Counter(S[i+1:])["R"]
            answer += a*b + c*d
            for j in range(1, min(i+1, N-i)):
                if S[i-j] != "B" and S[i+j] != "B" and S[i-j] != S[i+j]:
                    answer -= 1
        elif S[i] == "G":
            a = Counter(S[:i])["R"]
            b = Counter(S[i+1:])["B"]
            c = Counter(S[:i])["B"]
            d = Counter(S[i+1:])["R"]
            answer += a*b + c*d
            for j in range(1, min(i+1, N-i)):
                if S[i-j] != "G" and S[i+j] != "G" and S[i-j] != S[i+j]:
                    answer -= 1

print(answer)
### BUGGY CODE ###

import fractions
import math
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

N, M = [int(i) for i in input().split()]
A = [int(i)//2 for i in input().split()]

x = lcm(*A)
for a in A:
    if((x//a)%2==0):
        print(0)
        break
else:
    print(math.ceil((M//x)/2))



### FIXED CODE ###

# import fractions as math
import math

#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)

N, M = [int(i) for i in input().split()]
A = [int(i)//2 for i in input().split()]
lcm_A = 1
for a in A:
    lcm_A = lcm(lcm_A, a)
    if((lcm_A//a)%2==0):
        print(0)
        break
else:
    print(math.ceil((M//lcm_A)/2))
### BUGGY CODE ###

d=set()
for i in[0]*int(input()):d^={input()}
print(len(d))

### FIXED CODE ###

d={}
for _ in[0]*int(input()):
 i=input()
 d[i]=d.get(i,0)^1
print(sum(d.values()))
### BUGGY CODE ###

n,w=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
# wv.sort(key=lambda x:x[0])
# wv.sort(key=lambda x:-x[1])
# value[i][j] i番目までで重さがj以下となるように選んだときの価値の最大値
value=[[0 for _ in range(w+1)]for _ in range(n+1)]
for i in range(n):
    for j in range(w+1):
        if j-wv[i][0]>=0:
            value[i+1][j]=max(value[i][j],value[i][j-wv[i][0]]+wv[i][1])
        value[i+1][j]=max(value[i+1][j],value[i][j])

print(value[n][w])


### FIXED CODE ###


import numpy as np
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
value=np.zeros((n+1,w+1),dtype=int)
for i in range(n):
    wei=wv[i][0]
    value[i+1][:wei]=value[i][:wei]
    # np.maximum([1,-3,2],0) == [1,0,2]
    value[i+1][wei:]=np.maximum(value[i][wei:],value[i][:-wei]+wv[i][1])
# print(value)
print(value[n][w])
### BUGGY CODE ###

import sys
import numpy as np
from itertools import permutations
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

MOD = 1000000000 + 7

N, *X = map(int, read().split())
X = np.array(X)

cnt = 1
for i in range(1, N):
    cnt *= i

cnt %= MOD
ans = 0

l = list(permutations(range(1, N)))
for per in l:
    ans += np.abs(np.diff(np.array(list(per) + [N]))).sum()

ans /= len(l) 
ans *= cnt

print(int(ans % MOD))



### FIXED CODE ###

import sys
import numpy as np
from itertools import permutations
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

MOD = int(1e+9 + 7)


class Comb(object):
    def __init__(self, n, MOD=1e9+7):
        self.n = n
        self.MOD = MOD

        fac = [0] * self.n
        finv = [0] * self.n
        inv = [0] * self.n

        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1

        for i in range(2, n):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = MOD - inv[(MOD % i)] * (MOD // i) % MOD
            finv[i] = finv[i-1] * inv[i] % MOD
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def calv(self, k):
        if self.n < k:
            return 0

        return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.MOD) % self.MOD


N, *X = map(int, read().split())
X = np.array(X)
X_diff = np.diff(X)

comb = Comb(N+5, MOD)

acc = 0
ans = 0
for i in range(1, N):
    acc += comb.fac[N-1] * comb.inv[i]
    acc %= MOD

    ans += acc * (X_diff[i-1])
    ans %= MOD


print(ans % MOD)