Harryxun/stf_run huggingface dataset:
import math
a, b, c, d= list(map(int, input().split()))
m=0
for i in range(a,b+1):
	if i%c==0:
		x=1+math.floor((b-i)/c)
		break
for i in range(a,b+1):
	if i%d==0:
		y=1+math.floor((b-i)/d)
		break
for i in range(a,b+1):
	if i%(c*d)==0:
		z=1+math.floor((b-i)/(c*d))
		break
print(b-a+1-x-y+z)
# print(x, y, z)


### FIXED CODE ###

from fractions import gcd
a,b,c,d=map(int,input().split())
lenth=b-a+1

def lcm(m,n):
	return (m*n)//gcd(m,n)

def divnumber(c):
	ans=lenth//c
	rem1=a%c
	if rem1==0:rem1+=c
	rem2=lenth%c-1
	if rem1+rem2>=c:
		ans+=1
	return ans

print(lenth-divnumber(c)-divnumber(d)+divnumber(lcm(c,d)))
import sys


"""
# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

if __name__ == "__main__":
    N , M = map(int, sys.stdin.readline().split())
    A = [int(sys.stdin.readline()) for _ in range(M)]
    broken = [True if i in A else False for i in range(N + 1)]
    L = [0] * (N + 1)
    L[0] = 1
    if not broken[1]:
        L[1] = 1
    for i in range(2, N + 1):
        if not broken[i]:
            L[i] = L[i - 1] + L[i - 2]
    print(L[N] % mod)



### FIXED CODE ###

# n=int(input())
# a,b=map(int, input().split())
# c=list(map(int, input().split()))
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy
import itertools

mod  = 1000000007

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

broken = [0 for _ in range(N + 2)]

for i in range(M):
    n = int(input())
    broken[n] = True

dp = [0 for _ in range(N + 2)]
dp[N] = 1
for i in range(0, N)[::-1]:
    if broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i + 1] + dp[i + 2]) % mod

print(dp[0])
def a():return input()#s
def ai():return int(input())#a,n or k
def ma():return map(int, input().split())#a,b,c,d or n,k
def ms():return map(str, input().split())#,a,b,c,d
def lma():return list(map(int, input().split()))#x or y
def lms():return list(map(str, input().split()))#x or y
k= [0]
l = [0]
m=[]
co = range(1,10**5,2)
ce = range(0,10**5,2)
f = 1
def say(i):return print("Yes" if i == 0 else "No")
def Say(i):return print("YES" if i == 0 else "NO")
#def rep(i):return for i in range()
def addarray(k,l):
    for i in range(n+1):
        a ,b,c = map(int,input().split())
        k.append(a)
        l.append(b+c)
n = ai()
addarray(k,l)
for i in range(1,n):
    t = k[i]-k[i-1]
    if not t%2==1 and abs(l[i]-l[i-1]) in ce[:t//2+1]:
        f = 0
        break
    elif not t%2!=1 and abs(l[i]-l[i-1]) in co[:t//2+1]:
        f = 0
        break
say(f)
    

### FIXED CODE ###

def a():return input()#s
def ai():return int(input())#a,n or k
def ma():return map(int, input().split())#a,b,c,d or n,k
def ms():return map(str, input().split())#,a,b,c,d
def lma():return list(map(int, input().split()))#x or y
def lms():return list(map(str, input().split()))#x or y
k= [0]
l = [0]
m=[]
co = range(1,10**5+2,2)
ce = range(0,10**5+2,2)
f = 1
def say(i):return print("Yes" if i == 1 else "No")
def Say(i):return print("YES" if i == 0 else "NO")
#def rep(i):return for i in range()
def addarray(k,l):
    for i in range(n):
        a ,b,c = map(int,input().split())
        k.append(a)
        l.append(b+c)
n = ai()
addarray(k,l)
for i in range(1,n+1):
    t = k[i]-k[i-1]
    if t%2==1 and abs(l[i]-l[i-1]) in co[:t//2+1]:
        f = 1
    elif t%2==0 and abs(l[i]-l[i-1]) in ce[:t//2+1]:
        f = 1
    else:
        f = 0
        break
say(f)
n = int(input())
admission = list(map(int,input().split()))

for i in range(n):
    if admission[n] % 2 == 0:
        if admission[n] % 3 == 0 or admission[n] % 5 == 0:
            print("APPROVED")
        else:
            print("DENIED")

### FIXED CODE ###

n = int(input())
a = map(int,input().split())
for l in a:
    if l % 2 ==0:
        if l % 3 == 0 or l % 5 == 0:
            continue
        else:
            print("DENIED")
            quit()
print("APPROVED")
MOD=1000000007
N=int(input())
ls=[int(s) for s in input().split()]
RGB=[0,0,0]
ans=1
for i in range(N):
  x=RGB.count(ls[i])
  ans=(ans*x)%MOD
  y=RGB.index(ls[i])
  RGB[y]+=1
print(ans)

### FIXED CODE ###

MOD=1000000007
N=int(input())
ls=[int(s) for s in input().split()]
RGB=[0,0,0]
ans=1
for i in range(N):
  if ls[i] in RGB:
    x=RGB.count(ls[i])
    ans=(ans*x)%MOD
    y=RGB.index(ls[i])
    RGB[y]+=1
  else:
    ans=0
    break
print(ans)
from collections import Counter
w = list(Counter(list(input())).items())
if all(w[i][1]%2== for i in range(len(w))):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from collections import Counter
w = list(Counter(list(input())).items())
if all(w[i][1]%2==0 for i in range(len(w))):
    print("Yes")
else:
    print("No")
#!/usr/bin/env python3
import sys


def solve(x: int):

    if x == 1:
        return print('0')

    elif x == 0:
        return print('1')1


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    x = int(next(tokens))  # type: int
    solve(x)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(x: int):

    if x == 1:
        return print('0')

    elif x == 0:
        return print('1')


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    x = int(next(tokens))  # type: int
    solve(x)

if __name__ == '__main__':
    main()
s = input()
t = input()
l = 10**5
S = s*l

a = 0
flag = True
for i in range(len(t)):
    if t[i] in S:
        a = S.index(t[i], a)+1
    else:
        flag = False
        break
        
if flag:
    print(a)
else:
    print(-1)

### FIXED CODE ###

s = input()
t = input()
s_ = s[:]
cnt = 0
tlen = len(t)
ans = 0
flag = True

while cnt < tlen:
    
    num = s_.find(t[cnt])
    
    if num != -1:
        ans += (num+1)
        s_ = s_[(num+1):]
        cnt += 1
        flag = False
    else:
        if flag:
            print(-1)
            exit(0)
        ans += len(s_)
        s_ = s[:]
        flag = True
        
print(ans)
n = int(input())

def divisior(n):

    a = []
    i = 1

    while (i*i <= n):
        if n%i == 0:
            a.append(i)
            if (i*i == n): continue
            a.append(int(n/i))
        i += 1

    return a

ans = 0
a = divisior(n)

for x in a:
    if x == 1: continue
    tmp = n
    while (tmp%x == 0): tmp /= x
    if (tmp%x == 1) : ans += 1

b = divisior(n-1)

ans = ans + len(b) -1

print(ans)




### FIXED CODE ###


def swap(a ,b):
    x = 0
    x = a
    a = b
    b = x
    return a,b


str_number_list = input().split()
X = str_number_list[0]  #A
Y = str_number_list[1]  #B
Z = str_number_list[2]  #C

# swap(A,B)
X , Y = swap(X,Y)
#swap(A,C)
X,Z = swap(X,Z)
print("%s %s %s" % (X,Y,Z))
@pypy
n,k = map(int,input().split())
h = list(map(int, input().split()))

cnt = [0]*n
for i in range(1, n):
    cnt[i] = min(abs(h[m]-h[i])+cnt[m] for m in range(max(0, i-k), i))
print(cnt[n-1])


### FIXED CODE ###

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

cnt = [0]*n
for i in range(1, n):
    j = max(0,i-k)
    cnt[i] = min(abs(h[m]-h[i])+cnt[m] for m in range(j,i))
print(cnt[n-1])
# -*- coding:utf-8 -*-
import sys
from math import gcd

def f(a, x):
    """1以上a以下で、xで割り切れるものの数"""
    return a // x

def lcm(a, b):
    """ aとbの最小公倍数を返す """
    return a*b // gcd(a, b)

def solve():
    A, B, C, D = list(map(int, sys.stdin.readline().split()))
    A -= 1

    # CでもDでも割り切れないもの
    b = B - f(B, C) - f(B, D) + f(B, lcm(C, D))
    a = A - f(A, C) - f(A, D) + f(A, lcm(C, D))
    print(b-a)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

# -*- coding:utf-8 -*-
"""解説
B以下の整数のうち、CでもDでも割り切れないものの個数をCountBとする
A以下の整数のうち、CでもDでも割り切れないものの個数をCountAとする

求める答えは、CountB - CountA

・CountBの求め方
B以下の整数のうち、Cで割り切れるものの個数はCountB_C = B//C
B以下の整数のうち、Dで割り切れるものの個数はCountB_D = B//D
B以下の整数のうち、CでもDでも割り切れるものの個数はCountB_CD = B//lcm(C,D)

CountB = B - (CountB_C + CountB_D - CountB_CD)

"""
from fractions import gcd

def solve():
    A, B, C, D = list(map(int, input().split()))
    def lcm(a, b):
        """ aとbの最小公倍数を返す """
        return a*b // gcd(a, b)

    def f(x):
        """ 1以上x以下の整数のうち、CでもDでも割り切れないものの個数を返す """
        return x - (x//C + x//D - x//lcm(C,D))    

    ans = f(B) - f(A-1)

    print(ans)


if __name__ == "__main__":
    solve()
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
n, x, y = map(int, input().split())
x -= 1
y -= 1
GRAPH = [[0]*n for _ in range(n)]
for i in range(n-1):
    GRAPH[i][i+1] = GRAPH[i+1][i] = 1
GRAPH[x][y] = GRAPH[y][x] = 1
G = csr_matrix(GRAPH)
sp = shortest_path(G)

ans = [0]*(n-1)
for i in range(n):
    for j in range(i+1, n):
        path = int(sp[i][j])-1
        ans[path] += 1
print(*ans, sep="\n")


### FIXED CODE ###

n, x, y = map(int, input().split())
x -= 1
y -= 1
GRAPH = [[0]*n for _ in range(n)]

def shortest_path(i, j):
    if i <= x <= y <= j:
        return min(j-i, x-i+j-y+1)
    elif x <= i <= y <= j:
        return min(j-i, i-x+j-y+1)
    elif x <= i <= j <= y:
        return min(j-i, i-x+y-j+1)
    elif i <= x <= j <= y:
        return min(j-i, x-i+y-j+1)
    else:
        return j-i


ans = [0]*(n-1)
for i in range(n):
    for j in range(i+1, n):
        path = shortest_path(i, j)-1
        ans[path] += 1
print(*ans, sep="\n")
from heapq import heappush, heappop

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
cand = []

for i in range(len(A)):
    for j in range(len(B)):
        if(i + j + 1 >= K):
            break
        for k in range(len(C)):
            if(i + j + k + 1 >= K):
                break
            heappush(cand, A[i]+B[j]+C[k])
            if(len(cand) > K):
                heappop(cand)

ret = []
for i in range(K):
    ret.append(heappop(cand))

for i in reversed(range(K)):
    print(ret[i])
    


### FIXED CODE ###

from heapq import heappush, heappop

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
cand = []

for i in range(len(A)):
    for j in range(len(B)):
        if(i * j > K):
            break
        for k in range(len(C)):
            if(i *  j * k > K):
                break
            heappush(cand, A[i]+B[j]+C[k])
            if(len(cand) > K):
                heappop(cand)

ret = []
for i in range(K):
    ret.append(heappop(cand))

for i in reversed(range(K)):
    print(ret[i])
N = int(input())
A = list(map(int, input().split()))
A.sort()
print(sum(A[N + 1:2N + 1])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
print(sum(A[1:2 * N:2]))
rootList = [-1 for i in range(n)]
parent = [0 for i in range(n)]
lenList = [float("inf") for i in range(n)]
lenList[0] = 0
def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]

flag = True
while flag:
    flag = False
    edgeList.sort(key=lambda x: (x[0] + lenList[x[1]]))
    for e in edgeList:    # weight:e[0], e[1]->e[2]
        if e[2] == 0:
            continue
        x = getRoot(e[1])
        y = getRoot(e[2])
        if x == 0 != y:
            parent[e[2]] = e[1]
            lenList[e[2]] = lenList[e[1]] + e[0]
            rootList[y] = 0
            flag = True
            break

for i, j in zip(range(n), lenList):
    print(i, j)

### FIXED CODE ###

n = int(input())
edgeList = []
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(a[1]):
        edgeList.append([a[2*j+3], i, a[2*j+2]])
 
 
rootList = [-1 for i in range(n)]
parent = [0 for i in range(n)]
lenList = [float("inf") for i in range(n)]
lenList[0] = 0
def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
 
flag = True
while flag:
    flag = False
    edgeList.sort(key=lambda x: (x[0] + lenList[x[1]]))
    for e in edgeList:    # weight:e[0], e[1]->e[2]
        if e[2] == 0:
            continue
        x = getRoot(e[1])
        y = getRoot(e[2])
        if x == 0 != y:
            parent[e[2]] = e[1]
            lenList[e[2]] = lenList[e[1]] + e[0]
            rootList[y] = 0
            flag = True
            break
 
for i, j in zip(range(n), lenList):
    print(i, j)
from sys import stdin

def main():
    N, M = map(int, input().split())
    X = list(map(int, input().split()))

    if N >= M:
        print(0)
        return

    X.sort()
    n = [(i + 1, X[i+1] - X[i]) for i in range(M - 1)]
    n.sort(reverse=1, key=lambda x: x[1])
    ans, s1 = 0, 0
    for i in range(N - 1):
        s2 = n[i][0]
        ans += X[s1:s2][-1] - X[s1:s2][0]
        s1 = s2
    ans += X[s1:][-1] - X[s1:][0]
    print(ans)

input = lambda: stdin.readline()
main()


### FIXED CODE ###

from sys import stdin

def main():
    N, M = map(int, input().split())
    X = list(map(int, input().split()))

    if N >= M:
        print(0)
        return

    X.sort()
    n1 = [(i + 1, X[i+1] - X[i]) for i in range(M - 1)]
    n1.sort(reverse=1, key=lambda x: x[1])
    n2 = n1[:N-1]
    n2.sort()

    ans, i = 0, 0
    for j, _ in n2:
        ans += X[i:j][-1] - X[i:j][0]
        i = j
    ans += X[i:][-1] - X[i:][0]
    print(ans)

input = lambda: stdin.readline()
main()
n,m,k = map(int,input().split())
mod = 998244353
ans = 0

def comb(n,k,mod):
    nCk = 1

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= mod
 
    for i in range(1,k+1):
        nCk *= pow(i,mod-2,mod)
        nCk %= mod
    return nCk

a1 = pow(m-1, n-k-2, mod)  
b1 = 1  
for i in range(k,-1,-1):
    a = (a1*(m-1))%mod
    b = comb(n-1,i,mod)
    ans += a*b
ans *= m
print(ans%mod)

### FIXED CODE ###

n,m,k = map(int,input().split())
mod = 998244353
ans = 0

def comb(n, r, mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
  
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, n+1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)


for i in range(k+1):
    a = pow(m-1, n-i-1, mod)
    b = comb(n-1,i,mod)
    ans += (a*b)%mod
ans *= m
print(ans%mod)
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
import sys
def edge(S):
    e = defaultdict(lambda: set())
    for i in range(N+1):
        for j in S:
            e[i].add(i%j)
        e[i] = e[i] | {i}
    return e
def path(edge):
    p = defaultdict(lambda: set())
    for st in range(N+1):
        Q, p[st], new = [edge[st]]*3
        while Q:
            for j in Q:
                new = new | edge[j]
            Q = new - p[st]
            p[st] = p[st] | new
    return p

K = int(input())
A = inpl()
B = inpl()
for i in range(K):
    if A[i] < B[i]:
        print(-1)
        sys.exit()
if A == B:
    print(0)
    sys.exit()
N = max(A) 
T = []
for l in range(N,-1,-1):
    S = T + list(range(1,1+l))
    Pa = path(edge(S))
    for i in range(K):
        if B[i] not in Pa[A[i]]:
            break
    else:
        continue
    T.append(l+1)
if not T:
    print(2)
    sys.exit()
if N+1 in T:
    print(-1)
    sys.exit()
print(sum([2**i for i in T]))

### FIXED CODE ###

import sys
N = int(input())
a = [(int(v),i) for i, v in enumerate(input().split())]
ao = sum([v for v, i in a if i%2 and v>0])
ae = sum([v for v, i in a if not i%2 and v>0])
if max(ao, ae)== 0:
    ai = a.index(max(a))
    Ans = [1]*(ai)+list(range(N-ai,1,-1))
    print(max(a)[0])
    print(len(Ans))
    for i in Ans:
        print(i)
    sys.exit()
if ao >= ae:
    print(ao)
    yn = [i for v, i in a if i%2 and v>0]
else:
    print(ae)
    yn = [i for v, i in a if not i%2 and v>0]
listyn = [i in yn for i in range(N)]
Ans = []
while not listyn[0]:
    Ans.append(1)
    listyn = listyn[1:]
while not listyn[-1]:
    Ans.append(len(listyn))
    listyn = listyn[:-1]
while True:
    if len(listyn) == 1:
        break
    if len(listyn) == [2,3]:
        Ans.append(2)
        break
    if listyn[2]:
        Ans.append(2)
        listyn = [True] + listyn[3:]
    else:
        Ans.append(3)
        listyn = [True, False] + listyn[4:]
print(len(Ans))
for i in Ans:
    print(i)
import math
H,A = map(int, input().split)
print(math.ceil(H/A))

### FIXED CODE ###

import math

H,A = map(int, input().split())
print(math.ceil(H/A))
S  <>= raw_input()
SS = ">"+S+"<"
N = len(SS) - 1
A = [None for i in xrange(N)]

for i in xrange(N):
    if (SS[i] == ">" and SS[i+1] == "<"):
        A[i] = 0
        j = 0
        while (i-j-1)>=0 and SS[i-j] == ">":
            if A[i-j-1] == None:
                A[i-j-1] = j+1
            else:
                Max = max(A[i-j-1], j+1)
                A[i-j-1] = Max
            j += 1
        j = 0
        while (i+j+1)<N and SS[i+j+1] == "<":
            if A[i+j+1] == None:
                A[i+j+1] = j+1
            else:
                Max = max(A[i+j+1], j+1)
                A[i+j+1] = Max
            j += 1

print sum(A)            


### FIXED CODE ###


S  = raw_input()
SS = ">"+S+"<"
N = len(SS) - 1
A = [None for i in xrange(N)]

for i in xrange(N):
    if (SS[i] == ">" and SS[i+1] == "<"):
        A[i] = 0
        j = 0
        while (i-j-1)>=0 and SS[i-j] == ">":
            if A[i-j-1] == None:
                A[i-j-1] = j+1
            else:
                Max = max(A[i-j-1], j+1)
                A[i-j-1] = Max
            j += 1
        j = 0
        while (i+j+1)<N and SS[i+j+1] == "<":
            if A[i+j+1] == None:
                A[i+j+1] = j+1
            else:
                Max = max(A[i+j+1], j+1)
                A[i+j+1] = Max
            j += 1

print sum(A)
L, R = list(map(int,input().split()))

 if R - L >= 2019:
        print(0)
        exit()
 
ans = float('inf')
for i in range(L, R):
    for j in range(i+1, R+1):
        t = i*j%2019
        ans = min(ans,t)
print(ans)

### FIXED CODE ###

L, R = list(map(int,input().split()))

if(R - L) >= 2019:
    print(0)
    exit()
 
ans = float('inf')
for i in range(L, R):
    for j in range(i+1, R+1):
        t = i*j%2019
        ans = min(ans,t)
print(ans)
import sys
sys.setrecursionlimit(10*7)

def judge(c,l,r,counter):
  if counter == 0:
    return c
  elif len(c) == 0:
    return c
  else:
    return judge(list(filter(lambda x: l[0]<=x<=r[0],c)),l[1:],r[1:],counter-1)

def solve(c,l,r,m):
  return len(judge(c,l,r,m))
  
N,M = map(int,input().split())
L = [0]*M
R = [0]*M
for i in range(M):
  L[i],R[i] = map(int,input().split())
cards = range(1,N+1)
print(solve(cards,L,R,M))


### FIXED CODE ###

def solve(l,r):
  l_max = max(l)
  r_min = min(r)
  return max(r_min - l_max + 1, 0)
  
N,M = map(int,input().split())
L = [0]*M
R = [0]*M
for i in range(M):
  L[i],R[i] = map(int,input().split())
print(solve(L,R))
a = input().split(' ')
h1 = int(a[0])
h2 = int(a[1])
h3 = int(a[2])
 
if h1 < h3 && h3 < h2:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a = input().split(' ')
h1 = int(a[0])
h2 = int(a[1])
h3 = int(a[2])
 
if h1 < h3 and h3 < h2:
  print('Yes')
else:
  if h2 < h3 and h3 < h1:
    print('Yes')
  else:
    print('No')
#!/usr/bin/env python

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

whle k>0:
    if a>=b:
        b *= 2
    elif b>=c:
        c *= 2
    else:
        print('Yes')
        exit(0)
    k -= 1
print('No')


### FIXED CODE ###

#!/usr/bin/env python

ta, tb, tc = map(int, input().split())
k = int(input())

def dfs(s):
    a = ta
    b = tb
    c = tc
    if len(s) == k:
        #print(s)
        for i in range(k):
            if 'A' == s[i]:
                a *= 2
            elif 'B' == s[i]:
                b *= 2
            elif 'C' == s[i]:
                c *= 2
        if c > b > a:
            print('Yes')
            exit(0)
        return
    dfs(s+'A')
    dfs(s+'B')
    dfs(s+'C')

dfs('')

print('No')
import sys
N,M=map(int, input().split())
a=[]
b=[]
c=[]
for m in range (0,M):
  A,B,C=map(int, input().split() )
  a+=[A]
  b+=[B]
  c+=[C]
V=[0]*N# iに到達するときの最大得点
moji=[1]+[0]*(N-1)#infなら0をかえす
 
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        V[b[m]-1]=max(V[b[m]-1],V[a[m]-1]+c[m])
      else:
        V[b[m]-1]=V[a[m]-1]+c[m]
        moji[b[m]-1]=1

W=V[]
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        W[b[m]-1]=max(W[b[m]-1],W[a[m]-1]+c[m])
      else:
        W[b[m]-1]=W[a[m]-1]+c[m]
        moji[b[m]-1]=1
if V[N-1]==W[N-1]:
  print(V[N-1])
else:
  print("inf")

### FIXED CODE ###

import sys
N,M=map(int, input().split())
a=[]
b=[]
c=[]
for m in range (0,M):
  A,B,C=map(int, input().split() )
  a+=[A]
  b+=[B]
  c+=[C]
V=[0]+[-10**12]*(N-1)# iに到達するときの最大得点
 
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if V[b[m]-1]<V[a[m]-1]+c[m]:#共に有限の時はやる
      V[b[m]-1]=V[a[m]-1]+c[m]
 
moji2=[0]*N
for n in range(N):
  for m in range(M):
    u=a[m]
    v=b[m]
    if V[b[m]-1]<V[a[m]-1]+c[m]:#共に有限の時はやる
      V[b[m]-1]=V[a[m]-1]+c[m]
      moji2[b[m]-1]=1
      if moji2[N-1]:
        print("inf")
        sys.exit()
print(V[N-1])
N, M = map(int, input().split())
A = list(map(int, input().split()))

mmin = sum(A) * (4*M)
A.sort()

if A[m-1] < mmin:
  print('No')
else:
  print('Yes')

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
 
mmin = sum(A) / (4*M)
A.sort(reverse=True)
 
if A[M-1] < mmin:
  print('No')
else:
  print('Yes')
import itertools

n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
a.sort()
a=list(itertools.accumulate(a))
pin=0


lst=[1,1]
for i in range(2,n+10):
  lst.append((lst[-1]*i)%mod)

def combinations(n,r):
  xxx=lst[n]
  xxx*=pow(lst[n-r],mod-2,mod)
  xxx%=mod
  xxx*=pow(lst[r],mod-2,mod)
  xxx%=mod

  return xxx


for i in range(n-k+1):
  pin+=1
  now=n-k+1-i
  ans+=(a[-1]-a[-now-1]-a[now-1])*combinations(pin+k-3,k-2)
  ans%=mod


print(ans)

### FIXED CODE ###

import itertools

n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
a.sort()
a=list(itertools.accumulate(a))
pin=0


lst=[1,1]
for i in range(2,n+10):
  lst.append((lst[-1]*i)%mod)

def combinations(n,r):
  xxx=lst[n]
  xxx*=pow(lst[n-r],mod-2,mod)
  xxx%=mod
  xxx*=pow(lst[r],mod-2,mod)
  xxx%=mod

  return xxx

if k==1:
    print(0)
    exit()


for i in range(n-k+1):
  pin+=1
  now=n-k+1-i
  ans+=(a[-1]-a[-now-1]-a[now-1])*combinations(pin+k-3,k-2)
  ans%=mod


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

a = 0
for i in range(M):
  b = int(input())
  a += b

day = N-a
print(day)

### FIXED CODE ###

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

c = list(map(int,input().split()))
c_sum = sum(c)

day_count = N-c_sum

if day_count>=0:
  print(day_count)
else:
  print(-1)