Harryxun/stf_run huggingface dataset:
# D
N = int(input())
s = list(map(int, list(input())))

res = 0
i = 0



L = 0
for i in range(N):
    if s[i] == 1:
        L = i
        break
for i in range(N):
    if s[i] == 1:
        M = i        

        
def calc_add(temp_list):
    if len(temp_list) <= 1:
        return 0
    else:
        res = 0
        # use 101 for left
        dp_l = [0]*len(temp_list)
        # use 101 for right 
        dp_r = [0]*len(temp_list)
        # do not use 101
        dp_c = [0]*len(temp_list)
        for i in range(len(temp_list) - 1):
            if temp_list[i] > 1:
                dp_l[i+1] = max(dp_l[i] + temp_list[i] - 1, dp_c[i] + temp_list[i])
            else:
                dp_l[i+1] = dp_c[i] + temp_list[i]
            if temp_list[i] > 1:
                dp_r[i+1] = max(dp_l[i] + temp_list[i+1], dp_c[i] + temp_list[i+1], dp_r[i] + temp_list[i+1] - 1)
            else:
                dp_r[i+1] = dp_c[i] + temp_list[i+1]
            dp_c[i+1] = max(dp_l[i], dp_r[i], dp_c[i])
        
        return max(dp_l[-1], dp_r[-1], dp_c[-1])
    

cont0 = 1
cont00 = 1
temp_list = []

for i in range(L, M+1):
    if s[i] == 1:
        if cont0 == 1:
            temp_list.append(1)
            cont0 = 0
            cont00 = 0
        else:
            temp_list[-1] += 1
    else:
        if cont00 == 1:
            pass
        elif cont0 == 1:
            cont00 = 1
            res += calc_add(temp_list)
            temp_list = []
        else:
            cont0 = 1
            
    if i == M:
        res += calc_add(temp_list)
        temp_list = []
        
print(res)

### FIXED CODE ###

# D
N = int(input())
s = list(map(int, list(input())))

        
def calc_add(temp_list):
    if len(temp_list) <= 1:
        return 0
    else:
        res = 0
        # use 101 for left
        dp_l = [0]*len(temp_list)
        # use 101 for right 
        dp_r = [0]*len(temp_list)
        # do not use 101
        dp_c = [0]*len(temp_list)
        for i in range(len(temp_list) - 1):
            if temp_list[i] > 1:
                dp_l[i+1] = max(dp_l[i] + temp_list[i] - 1, dp_c[i] + temp_list[i])
            else:
                dp_l[i+1] = dp_c[i] + temp_list[i]
            if temp_list[i] > 1:
                dp_r[i+1] = max(dp_l[i] + temp_list[i+1], dp_c[i] + temp_list[i+1], dp_r[i] + temp_list[i+1] - 1)
            else:
                dp_r[i+1] = dp_c[i] + temp_list[i+1]
            dp_c[i+1] = max(dp_l[i], dp_r[i], dp_c[i])
        
        return max(dp_l[-1], dp_r[-1], dp_c[-1])
    

cont0 = 1
cont00 = 1
temp_list = []
res = 0

for i in range(N):
    if s[i] == 1:
        if cont0 == 1:
            temp_list.append(1)
            cont0 = 0
            cont00 = 0
        else:
            temp_list[-1] += 1
    else:
        if cont00 == 1:
            pass
        elif cont0 == 1:
            cont00 = 1
            res += calc_add(temp_list)
            temp_list = []
        else:
            cont0 = 1
            
    if i == N - 1:
        res += calc_add(temp_list)
        
print(res)
# -*- coding: utf-8 -*-

import numpy as np

EDPC = "https://atcoder.jp/contests/DP/"
TDPC = "https://atcoder.jp/contests/tDPc/tasks"

############### TESTCASE ###############
test = ""
#test = \
"""
3 8
3 30
4 50
5 60
ans 90
"""

"""
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
ans 5000000000(>int32)
"""

"""
6 15
6 5
5 6
6 4
6 6
3 5
7 2
ans 17
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################
#np.maximum(*arrays) == np.max(np.vstack(*arrays), axis=0)
#(np.maximum(np.array([1,3,2]), np.array([2, 1, 3])) == 
# np.max(np.vstack([np.array([1,3,2]), np.array([2, 1, 3])]), axis=0)).all()
################# MAIN #################

N, W = map(int, input2().split())
WV = np.array([tuple(map(int, input2().split())) for _ in range(N)])

dp = np.zeros(W + 1)
for w, v in WV:
    dp[W:w-1:-1] = np.max(np.vstack([dp[W:w-1:-1], dp[W-w::-1] + v]), axis=0)
    
print(dp[-1])


### FIXED CODE ###

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

import numpy as np

EDPC = "https://atcoder.jp/contests/DP/"
TDPC = "https://atcoder.jp/contests/tdpc/tasks"

############### TESTCASE ###############
test = ""
#test = \
"""
3 8
3 3
4 5
5 6
ans 9
"""

"""
6 15
6 5
5 6
6 4
6 6
3 5
7 2
ans 17
"""

"""
N<100, W<10*9
wi<10**9, vi<10**3 
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################
#np.maximum(*arrays) == np.max(np.vstack(*arrays), axis=0)
#(np.maximum(np.array([1,3,2]), np.array([2, 1, 3])) == 
# np.max(np.vstack([np.array([1,3,2]), np.array([2, 1, 3])]), axis=0)).all()
################# MAIN #################

N, W = map(int, input2().split())
WV = np.array([tuple(map(int, input2().split())) for _ in range(N)], dtype="int64")
Wsum = np.sum(WV[:, 0])
Vsum = np.sum(WV[:, 1])

dp = np.full(Vsum+1, Wsum, dtype="int64")
for w, v in WV:
    dp[:Vsum-v+1] = np.min(np.vstack([dp[:Vsum-v+1], dp[v:] - w]), axis=0)
    
print(np.where(dp < W+1)[0][-1])
import copy
import fractions
N=int(input())
A=list(map(int,input().split()))
ans=[]
def dfs(A):
  l=[]
  if len(A)==1:
    return A[0]
  for i in range(0,len(A),2):
    l.append(fractions.gcd(A[i],A[i+1]))
  return dfs(l)
  
  
for i in range(N):
  s=copy.deepcopy(A)
  s.pop(i)
  ans.append(dfs(s))

print(max(ans))

### FIXED CODE ###

import copy
import fractions
N=int(input())
A=list(map(int,input().split()))
ans=[]
L=[0 for i in range(N)]
R=[0 for i in range(N)]
for i in range(N):
  if i != 0:
    L[i]=fractions.gcd(L[i-1],A[i-1])
    R[N-1-i]=fractions.gcd(R[N-i],A[N-i])

for i in range(N):
  ans.append(fractions.gcd(L[i],R[i]))

print(max(ans))
# N,Mの把握
l = list(map(int, input().split()))
N = l[0]
M = l[1]

#list(map(str, input().split()))をM回くりかえし、１つのリストにまとめる。

c = []
for i in range(M):
	c = c + list(map(int, input().split()))

# リストを指定の番号で検索して、項目数を返す関数
def r(x):
	y = str(c.count(x))
	return y

#都市番号1からNまでリストを検索し、出力
dic = {}
for i in range(1,N+1):
	print(r(i))

### FIXED CODE ###

list = list(map(int, input().split()))
if list[2] >= list[0] and list[2] <= list[1]:
	print('Yes')
else:
	print('No')
n = int(input())

if(n == 0):
    printf(1)
if(n == 1):
    printf("0")

### FIXED CODE ###

n = int(input())

if(n == 0):
    print(1)
elif(n == 1):
    print(0)
N, M = map(int, input().split())
A = [input() for _ in range(N)]
B = [input() for _ in range(M)]

for y in range(N-M+1):
    for x in range(N-M+1):
        for k in range(M):
            if A[y+k][x:x+M] != B[y]:
                break
        else:
            print("Yes")
            exit()
print("No")

### FIXED CODE ###

import sys

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

for y in range(N-M+1):
    for x in range(N-M+1):
        for k in range(M):
            if A[y+k][x:x+M] != B[k]:
                break
        else:
            print("Yes")
            sys.exit()
print("No")
from collections import defaultdict

def possible():
    if N%2==0:
        for cnt in cnt_dict.values():
            if cnt != 2:
                return False
        return True
    else:
        for i, cnt in enumerate(cnt_dict.values()):
            if i==0:
                if cnt != 1:
                    return False
            else:
                if cnt != 2:
                    return False
        return True

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

cnt_dict = defaultdict(list)

if N%2==0:
    for i in range(1, N, 2):
        cnt_dict[i] = 0
else:
    for i in range(0, N, 2):
        cnt_dict[i] = 0
for a in A:
    cnt_dict[a]+=1

if __name__ == "__main__":    

    if possible():
        mod = 10**9+7
        res = 1
        for i in range(1, num+1):
            res = res*2%mod
        print(res)
    else:
        print(0)

### FIXED CODE ###

from collections import defaultdict

def possible():
    if N%2==0:
        for cnt in cnt_dict.values():
            if cnt != 2:
                return False
        return True
    else:
        for i, cnt in enumerate(cnt_dict.values()):
            if i==0:
                if cnt != 1:
                    return False
            else:
                if cnt != 2:
                    return False
        return True

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

cnt_dict = defaultdict(list)

if N%2==0:
    for i in range(1, N, 2):
        cnt_dict[i] = 0
else:
    for i in range(0, N, 2):
        cnt_dict[i] = 0
for a in A:
    if not(a in cnt_dict.keys()):
        flag=False
    else:
        cnt_dict[a]+=1
        flag=True

if __name__ == "__main__":    

    if possible() and flag:
        mod = 10**9+7
        res = 1
        for i in range(1, num+1):
            res = res*2%mod
        print(res)
    else:
        print(0)
n, m = [0] * 2

def format_input(filename = None):
	global n, m
	if filename == None:
		n, m = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(3, 10**5)
		m = rng(1, (n-1) // 2)
		print(n, m)

def get_answer():
	unused = list(range(n))

	for i in range(m):
		a = unused[0]
		b = unused[0]+i+1
		unused.remove(a)
		unused.remove(b)
		print(a+1, b+1)	


if __name__ == '__main__':
	format_input()

	get_answer()


### FIXED CODE ###



n, m = [0] * 2

def format_input(filename = None):
	global n, m
	if filename == None:
		n, m = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(3, 10**5)
		m = rng(1, (n-1) // 2)
		print(n, m)

def get_answer():
	median = n // 2

	for i in range(m):
		if n % 2 == 0 and i >= n // 4:
			print(median-i, median+i+2)
		else:
			print(median-i, median+i+1)


if __name__ == '__main__':
	format_input()

	get_answer()
# -*- coding: utf-8 -*-
import fractions
import copy
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

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

gcds = list()
for i in range(0,N):
    B = copy.deepcopy(A)
    B.pop(i)
    tmp = gcd_list(B)
    gcds.append(tmp)

print(max(gcds))


### FIXED CODE ###

# -*- coding: utf-8 -*-
A = list(map(int,input().split()))
print(A[2] // A[0] * A[1])
# 1.A_C間,B_D間に##となっているマスがないこと
# 2.D>CまたはDの周辺に#がないまたはB_D間に...があること
n, a, b, c, d = map(int, input().split())
s = " " + input()
Triple_floor = False
Triple_floor = False
before_stat = ""
floor_num = 0
counter = a+1
for char in s[a+1:]:
    if(counter > c and counter > d):
        # この先はどうでもいい.
        break
    if(char == "."):
        floor_num += 1
        if(floor_num >= 3 and counter > (b+1) and counter <= (d+1)):
            Triple_floor = True
    else:
        floor_num = 0
        if(before_stat == "#"):
            print("No")
            exit(1)
    before_stat = char
    counter += 1
if(c<d or Triple_floor):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

# 1.A_C間,B_D間に##となっているマスがないこと
# 2.D>CまたはDの周辺に#がないまたはB_D間に...があること
n, a, b, c, d = map(int, input().split())
s = " " + input()
Triple_floor = False
before_stat = ""
floor_num = 0
counter = a
for char in s[a:]:
    if(counter > max(c,d)):
        # この先はどうでもいい.
        break
    if(char == "."):
        floor_num += 1
        if(floor_num >= 3 and counter >= (b+1) and counter <= (d+1)):
            Triple_floor = True
    else:
        floor_num = 0
        if(before_stat == "#"):
            c=d
            Triple_floor = False
            break
    before_stat = char
    counter += 1
if(c<d or Triple_floor):
    print("Yes")
else:
    print("No")
s = input().split()
n=int(s[0])

s=(input().split())

list=[[0 for i in range(2)] for j in range(n)]


for i in range(n):
    list[i][1]=i
    list[i][0]=int(s[i])

list.sort()

#print('list = {}'.format(list))
answer=[]
for i in range(n):
    print(list[i][1]+1)
    #list.append(list[i][1]+1)

#print(answer)


### FIXED CODE ###

N = int(input())
print(1 - (N//2)/N)
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
# print(A)
ans = A[0]
if N >= 3:
    a = (N - 2) // 2
    b = (N - 2)  % 2
# print(a)
# print(b)
if b == 0:
    for i in range(a):
        ans += (A[i+1] * 2)
else:
    for i in range(a):
        ans += (A[i+1] * 2)
    ans += A[a+1]
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
# print(A)
ans = A[0]
if N >= 3:
    a = (N - 2) // 2
    b = (N - 2)  % 2
# print(a)
# print(b)
    if b == 0:
        for i in range(a):
            ans += (A[i+1] * 2)
    else:
        for i in range(a):
            ans += (A[i+1] * 2)
        ans += A[a+1]
print(ans)
from sys import setrecursionlimit as srl; srl(10**7)
rr = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

N =int(rr())
from collections import Counter
count = Counter()
for _ in xrange(N):
    count[rr()] += 1
M = max(count.values())
ans = []
for k in count:
    if count[k] == M:
        ans.append(k)
ans.sort()
for x in ans:
    print x


### FIXED CODE ###

from sys import setrecursionlimit as srl; srl(10**7)
rr = raw_input
rrm = lambda: map(int, raw_input().split())

N =int(rr())
from collections import Counter
count = Counter()
for _ in xrange(N):
    count[rr()] += 1
M = max(count.values())
ans = []
for k in count:
    if count[k] == M:
        ans.append(k)
ans.sort()
for x in ans:
    print x
s = input()
ans = "WA"
tmp =""
if s[0] == 'A':
    if s[2:-1].count("C") ==1:
        tmp = s.replace("A","a").replace("C."c)
        if tmp = s.lower():
            ans = "AC"
print(ans)

### FIXED CODE ###

s = input()
ans = "WA"
tmp =""
if s[0] == 'A':
    if s[2:-1].count("C") ==1:
        tmp = s.replace("A","a").replace("C","c")
        if tmp == s.lower():
            ans = "AC"
print(ans)
import math
import sys

x1, y1, x2, y2 = [int(x) for x in sys.stdin.readline().split()]
print(math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2))

### FIXED CODE ###

import math
import sys

x1, y1, x2, y2 = [float(x) for x in sys.stdin.readline().split()]
print(math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2))
import collections

n = int(input())
odd = []
even = []
for i, j in enumerate(map(int, input().split())):
    if i % 2 == 0:
        even += [j]
    else:
        odd += [j]
odd = sorted(collections.Counter(odd).items(), reverse=True, key=lambda x: x[1])
even = sorted(collections.Counter(even).items(), reverse=True, key=lambda x: x[1])

if len(odd) == 1 and len(even) == 1 and odd[0][0] == even[0][0]:
    print(n // 2)
elif odd[0][0] == even[0][0]:
    if odd[0][1] == even[0][1]:
        for i in range(n//2):
            if odd[i][1] == even[i][1]:
                continue
            elif odd[i][1] > even[i][1]:
                print((n // 2 - odd[0][1]) + (n // 2 - even[1][1]))
            elif odd[i][1] < even[i][1]:
                print((n // 2 - odd[1][1]) + (n // 2 - even[0][1]))
        else:
            print((n // 2 - odd[0][1]) + (n // 2 - even[1][1]))
    elif odd[0][1] > even[0][1]:
        print((n // 2 - odd[0][1]) + (n // 2 - even[1][1]))
    elif odd[0][1] < even[0][1]:
        print((n // 2 - odd[1][1]) + (n // 2 - even[0][1]))
else:
    print((n // 2 - odd[0][1]) + (n // 2 - even[0][1]))


### FIXED CODE ###

import collections

n = int(input())
odd = []
even = []
for i, j in enumerate(map(int, input().split())):
    if i % 2 == 0:
        even += [j]
    else:
        odd += [j]
odd = sorted(collections.Counter(odd).items(), reverse=True, key=lambda x: x[1])
even = sorted(collections.Counter(even).items(), reverse=True, key=lambda x: x[1])

if len(odd) == 1 and len(even) == 1 and odd[0][0] == even[0][0]:
    print(n // 2)
elif odd[0][0] == even[0][0]:
    if odd[0][1] == even[0][1]:
        for i in range(2):
            if odd[i][1] == even[i][1]:
                continue
            elif odd[i][1] > even[i][1]:
                print((n // 2 - odd[1][1]) + (n // 2 - even[0][1]))
                break
            elif odd[i][1] < even[i][1]:
                print((n // 2 - odd[0][1]) + (n // 2 - even[1][1]))
                break
        else:
            print((n // 2 - odd[0][1]) + (n // 2 - even[1][1]))
else:
    print((n // 2 - odd[0][1]) + (n // 2 - even[0][1]))
import sys
input = sys.stdin.readline


def gcd(a, b):
    a, b = max(a, b), min(a, b)
    if b == 0:
        return a
    return gcd(b, a % b)


def main():
    n = int(input())
    A = list(map(int, input().split()))
    gcdA = [0]*n
    gcdB = [0]*n
    gcdA[0] = A[0]
    gcdB[0] = A[n-1]
    for i in range(1, n):
        gcdA[i] = gcd(A[i], gcdA[i-1])
        gcdB[i] = gcd(A[n-i-1], gcdB[n-1])
    ans = max(gcdA[n-2], gcdB[1])
    for i in range(1, n):
        ans = max(ans, gcd(gcdA[i-1], gcdB[i+1]))
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#import sys
#input=sys.stdin.readline

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    if b == 0:
        return a
    return gcd(b, a % b)


def main():
    n = int(input())
    A = list(map(int, input().split()))
    gcdA = [0]*n
    gcdB = [0]*n
    gcdA[0] = A[0]
    gcdB[n-1] = A[n-1]
    for i in range(1, n):
        gcdA[i] = gcd(A[i], gcdA[i-1])
        gcdB[n-i-1] = gcd(A[n-i-1], gcdB[n-i])
    ans = max(gcdA[n-2], gcdB[1])
    for i in range(1, n-1):
        ans = max(ans, gcd(gcdA[i-1], gcdB[i+1]))
    print(ans)


if __name__ == "__main__":
    main()
def main():
    N = int(input())
    A = list(map(int, input().split()) for _ in range(N))

    for e in A:
        if e % 2 == 0 and e % 3 != 0 and e % 5 != 0:
            print("DENIED")
            exit(0)

    print("APPROVED")


if __name__ == "__main__":
    main()


### FIXED CODE ###

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

    even = []

    for e in A:
        if e % 2 == 0:
            even.append(e)


    for e in even:
        if e % 3 != 0 and e % 5 != 0:
            print("DENIED")
            exit(0)

    print("APPROVED")


if __name__ == "__main__":
    main()
import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
 
new_list_f = sorted(F)
new_list_a = sorted(A, reverse=True)

new_list_f = np.array(new_list_f)
new_list_a = np.array(new_list_a)
time = new_list_f * new_list_a
 
for i in range(K + 1):
  t_max = time.index(max(time))
  new_list_a[t_max] = new_list_a[t_max] - (i - (i - 1))
  if new_list_a[t_max] == 0:
    break
  
print(time)

### FIXED CODE ###

import numpy as np

import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
A = np.array(input().split(), np.int64)
F = np.array(input().split(), np.int64)

A.sort()
F.sort()

F= F[::-1]

left = -1
right = (A * F).sum()
while left + 1 < right:
  middle = (left + right) // 2
  right_arr = np.maximum(0, A - middle // F).sum() <= K
  if right_arr:
    right = middle
  else:
    left = middle
print(right)
inp=input()
abl=inp.split()
map(int,abl)
a,b=list(map(int,abl))

print(a*b,2(a+b))


### FIXED CODE ###

a,b=map(int,input().split())
print(a*b,2*(a+b))
from collections import Counter

def Get_nC2(n):
    return int(n*(n-1) / 2)


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

c = Counter(A_i)
cnt_dict = {}

total = sum(list(map(Get_nC2, tmp.values())))

for a_i in A_i:
    result =  total - Get_nC2(c[a_i]) + Get_nC2(c[a_i-1])
    print(result)


### FIXED CODE ###

from collections import Counter

def Get_nC2(n):
    return int(n*(n-1) / 2)


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

c = Counter(A_i)


total = sum(list(map(Get_nC2, c.values())))

for a_i in A_i:
    result =  total - Get_nC2(c[a_i]) + Get_nC2(c[a_i]-1)
    print(result)
k = input()

if k%2 ==0:
    print((k/2)**2)
else:
    print(((k-1)/2)*((k+1)/2))


### FIXED CODE ###

k = int(input())


if k%2 ==0:
    print(int((k/2)*(k/2)))
else:
    print(int(((k-1)/2)*((k+1)/2)))
s = list(input()).sort()
t = list(input()).sort()
ns = len(s)
nt = len(t)
can = True
if(ns<nt):
    for i in range(ns):
        if(s[i] > t[i]):
            can = False
            break
        if(s[i] < t[i]):
            can = True
            break
else:
    can = False
    for i in range(nt):
        if(s[i] > t[i]):
            can = False
            break
        if(s[i] < t[i]):
            can = True
            break
if(can):
    print('Yes')
else:
    print('No')



### FIXED CODE ###

s = ''.join(sorted(input()))
t = ''.join(sorted(input(),reverse=True))
if(s<t):
    print('Yes')
else:
    print('No')
N, K = list(map(int, input().split()))
p = list(map(int, input().split()))

# cumulated value
c_p = [0] * N
c_p[0] = p[0]

for i in range(1, N):
    c_p[i] = c_p[i - 1] + p[i]

max_e = 0

for i in range(N - K + 1):
    e = c_p[i + K] - c_p[i]
    if e > max_e:
        max_e = e

print((max_e + K) / 2)


### FIXED CODE ###

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

# cumulated value
c_p = [0] * N
c_p[0] = p[0]

for i in range(1, N):
    c_p[i] = c_p[i - 1] + p[i]

max_e = c_p[K - 1]

for i in range(K, N):
    e = c_p[i] - c_p[i - K]
    max_e = max(max_e, e)

print((max_e + K) / 2)
n,m=map(int,input())
a=list(map(int,input().split()))
b=sum(a)
print(max(0,n-b))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
b=sum(a)
print(max(-1,n-b))
n, k = map(int, input().split())

t = [0]*n
for i in range(k):
  d = int(input())
  A = list(map(int, input().split()))
  for a in range A:
    t[a - 1] += 1
print(t.count(0))

### FIXED CODE ###

n, k = map(int, input().split())
 
t = [0]*n
for i in range(k):
  d = int(input())
  A = list(map(int, input().split()))
  for a in A:
    t[a - 1] += 1
print(t.count(0))
a = str(input())
b = 0
for i in range(4):
if a[i]==2:
b=b+1
else:
b=b

print(b)


### FIXED CODE ###

a = input()
a = str(a)
b = 0
for i in range(len(a)):
    if a[i]=="2":
        b=b+1
    else:
        b=b
print(b)
N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

a_sum = sum([item[0] for item in items])
b_sum = sum([item[1] for item in items])
inf = float("inf")
dp = [[[inf for _ in range(a_sum + 20)] for _ in range(b_sum + 20)] for i in range(N + 1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(a_sum):
        for b in range(b_sum):
            if dp[i + 1][a][b] > dp[i][a][b]:
                dp[i + 1][a][b] = dp[i][a][b]
            if dp[i + 1][a + items[i][0]][b + items[i][1]] > dp[i][a][b] + items[i][2]:
                dp[i + 1][a + items[i][0]][b + items[i][1]] = dp[i][a][b] + items[i][2]

ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

a_sum = sum([item[0] for item in items])
b_sum = sum([item[1] for item in items])
inf = float("inf")
dp = [[[inf for _ in range(a_sum + 100)] for _ in range(b_sum + 100)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(a_sum + 1):
        for b in range(b_sum + 1):
            dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])
            dp[i + 1][a + items[i][0]][b + items[i][1]] = min(dp[i + 1][a + items[i][0]][b + items[i][1]],
                                                              dp[i][a][b] + items[i][2])
ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)
from  math import gcd
import math
a,b,c,d=map(int,input().split())
def k(n):
    aa=n//c
    bb=n//d
    f=n//((c*d)//math.gcd(c,d))
    return n-aa-bb+f
print(k(b)-k(a-1))

### FIXED CODE ###

from fractions import gcd
A,B,C,D = map(int,input().split())
def f(n):
    x = n//C
    y = n//D
    z = n//(C*D//gcd(C,D))
    return n - x - y + z

print(f(B) - f(A-1))