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

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

if N == 1:
	if a[0] >= K:
		print(0)
	else:
		print(1)

else:
	def check(i):
		if a[i] >= K:
			return True
		if i == 0:
			b = a[1:]
		elif i == N - 1:
			b = a[:N - 1]
		else:
			b = a[:i] + a[i+1:]
		#print(b)
		#ok = False
		#dp = [[False] * K for _ in range(N - 1)]
		dp = [False] * K
		#dp[0] = True
		if b[0] < K:
			#dp[0][b[0]] = True
			dp[b[0]] = True
		if K - a[i] <= b[0] < K:
			return True
		for j in range(1, N - 1):

			#dp2 = [False] * K
			#if b[j] < K:
				#dp[b[j]] = True
			for k in range(K - 1, 0, -1):
				#if b[j] == K:
				#	return True
				#elif dp[j - 1][k] == True:
				#if dp[k] == True:
					#dp2[k] = True
				
				#elif k > b[j]:
				
				if k >= b[j]:
					#if dp[j - 1][k - b[j]] == True:
					if dp[k - b[j]] == True:
						#dp[j][k] = True
						dp[k] = True

				#if dp[j][k] == True and K - a[i] <= k < K:
				if dp[k] == True and K - a[i] <= k:
					return True

			#print(dp)
			#dp = dp2

		return False


	def bi_search(lower, upper):
		#print(lower, upper)
		mid = (lower + upper) // 2
		#print(mid)
		if mid == 0 and check(mid) == True:
			return 0
		elif mid == N - 2 and check(mid + 1) == False:
			return N
		elif check(mid) == False and check(mid + 1) == True:
			#print("hoge")
			return mid + 1
		elif check(mid) == True:
			return bi_search(lower, mid)
		else:
			return bi_search(mid, upper)


	print(bi_search(0, N - 1))


### FIXED CODE ###

import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if check(1):
    print(0)
    sys.exit()

if not check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)
### BUGGY CODE ###

S = input()
N = len(S)
mod = 10**9+7

num_q = [0]
res = 0
for i in range(N):
    if S[i] == "?":
        res += 1
    num_q.append(res)

# それぞれi番目までのa,a-b,a-b-cの数
dp_a = [0]*(N+1)
dp_ab = [0]*(N+1)
dp_abc = [0]*(N+1)

for i in range(1,N+1):
    if S[i-1] == "A":
        dp_a[i] = dp_a[i-1] + 3**num_q[i-1]
        dp_ab[i] = dp_ab[i-1]
        dp_abc[i] = dp_abc[i-1]
        
    elif S[i-1] == "B":
        dp_a[i] = dp_a[i-1]
        dp_ab[i] = dp_ab[i-1] + dp_a[i-1]
        dp_abc[i] = dp_abc[i-1]
        
    elif S[i-1] == "C":
        dp_a[i] = dp_a[i-1]
        dp_ab[i] = dp_ab[i-1]
        dp_abc[i] = dp_abc[i-1] + dp_ab[i-1]
        
    elif S[i-1] == "?":
        dp_a[i] = dp_a[i-1] * 3 + 3**num_q[i-1]
        dp_ab[i] = dp_ab[i-1] * 3 + dp_a[i-1] 
        dp_abc[i] = dp_abc[i-1] * 3 + dp_ab[i-1]
        
    dp_a[i] %= mod
    dp_ab[i] %= mod
    dp_abc[i] %= mod
        
print(dp_abc[N])



### FIXED CODE ###

S = input()
#S = "????C?????B??????A???????"
N = len(S)
mod = 10**9+7

num_q = [1]
res = 1
for i in range(N):
    if S[i] == "?":
        res = res*3 % mod
    num_q.append(res)
    

# それぞれi番目までのa,a-b,a-b-cの数
dp_a = [0]*(N+1)
dp_ab = [0]*(N+1)
dp_abc = [0]*(N+1)

for i in range(1,N+1):
    if S[i-1] == "A":
        dp_a[i] = dp_a[i-1] + num_q[i-1]
        dp_ab[i] = dp_ab[i-1]
        dp_abc[i] = dp_abc[i-1]
        
    elif S[i-1] == "B":
        dp_a[i] = dp_a[i-1]
        dp_ab[i] = dp_ab[i-1] + dp_a[i-1]
        dp_abc[i] = dp_abc[i-1]
        
    elif S[i-1] == "C":
        dp_a[i] = dp_a[i-1]
        dp_ab[i] = dp_ab[i-1]
        dp_abc[i] = dp_abc[i-1] + dp_ab[i-1]
        
    elif S[i-1] == "?":
        dp_a[i] = dp_a[i-1] * 3 + num_q[i-1]
        dp_ab[i] = dp_ab[i-1] * 3 + dp_a[i-1] 
        dp_abc[i] = dp_abc[i-1] * 3 + dp_ab[i-1]
        
    dp_a[i] %= mod
    dp_ab[i] %= mod
    dp_abc[i] %= mod
        
print(dp_abc[N])
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
for i in range(len(P)):
    P[i] -= 1

dp = [[1 + min(i, N - 1 - i, j, N - 1 - j) for j in range(N + 1)] for i in range(N + 1)]

presence = [[1 for j in range(N)] for i in range(N)]

ans = 0
for i in range(len(P)):
    x = P[i] // N
    y = P[i] % N
    ans += dp[x][y] - 1
    presence[x][y] = 0

    Q = [(x, y)]
    while Q:
        x, y = Q.pop()
        new_value = presence[x][y] + min(
            dp[x - 1][y], dp[x + 1][y], dp[x][y - 1], dp[x][y + 1]
        )
        if new_value != dp[x][y]:
            dp[x][y] = new_value
            if 1 <= x:
                Q.append((x - 1, y))
            if x < N - 1:
                Q.append((x + 1, y))
            if 1 <= y:
                Q.append((x, y - 1))
            if y < N - 1:
                Q.append((x, y + 1))

print(ans)

### FIXED CODE ###

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

dp = [[min(i, N - i - 1, j, N - j - 1) for j in range(N)] for i in range(N)]

presence = [[1 for j in range(N)] for i in range(N)]

ans = 0
for i in range(len(P)):
    P[i] -= 1
    x, y = divmod(P[i], N)
    ans += dp[x][y]
    presence[x][y] = 0

    Q = [(x, y)]
    while Q:
        x, y = Q.pop()
        new_value = dp[x][y] + presence[x][y]
        if 1 <= x and dp[x - 1][y] > new_value:
            dp[x - 1][y] = new_value
            Q.append((x - 1, y))
        if x < N - 1 and dp[x + 1][y] > new_value:
            dp[x + 1][y] = new_value
            Q.append((x + 1, y))
        if 1 <= y and dp[x][y - 1] > new_value:
            dp[x][y - 1] = new_value
            Q.append((x, y - 1))
        if y < N - 1 and dp[x][y + 1] > new_value:
            dp[x][y + 1] = new_value
            Q.append((x, y + 1))


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

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

def calc(n):
    return sum([i for i in range(1, n+1)]) / n

ex = []
for i in p:
    ex.append(calc(i))
max_ex = 0
for i in range(0, N-(K-1)):
    temp = sum(ex[i:i+K])
    if temp >= max_ex:
        max_ex = temp

print(max_ex)

### FIXED CODE ###

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

Es = [(1+p_i)/2 for p_i in p]

t = sum(Es[0:k])
ans = t

for i in range(n-k):
    t -= Es[i]
    t += Es[i+k]
    ans = max(ans,t)

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

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

for i in range(k):
    m = li.index(max(li))
    li[m] = 0

print(sum(li))

### FIXED CODE ###

n,k = map(int,input().split())
li = list(map(int,input().split()))
ls = sorted(li, reverse=True)
if k >= len(li):
    print(0)
else:
    print(sum(ls[k:]))
### BUGGY CODE ###

from collections import deque

h , w = map(int,input().split())
cou = 0
ma = []
for i in range(h):
    kar = list(input())
    cou += kar.count("#")
    ma.append(kar)


ans = [[-1 for i in range(w)] for j in range(h)]
ans[0][0] = 1
q = deque([(0,0)])
xy = [(1,0),(-1,0),(0,1),(0,-1)]

while q:
    x , y = q.popleft()
    ma[x][y] = "#"
    for i in range(4):
        nx = x + xy[i][0]
        ny = y + xy[i][1]
        if 0 <= nx <= h-1 and 0 <= ny <= w-1:
            if ma[nx][ny] == ".":
                q.append((nx,ny))
                ans[nx][ny] = ans[x][y] + 1
        if nx == h-1 and ny == w-1:
            break

if ans[h-1][w-1] == -1:
    print(-1)
else:
    print(h*w - cou - ans[h-1][w-1])

### FIXED CODE ###

from collections import deque
 
h , w = map(int,input().split())
cou = 0
ma = []
for i in range(h):
    kar = list(input())
    cou += kar.count("#")
    ma.append(kar)
 
 
ans = [[-1 for i in range(w)] for j in range(h)]
ans[0][0] = 1
q = deque([(0,0)])
xy = [(1,0),(-1,0),(0,1),(0,-1)]
 
while q:
    x , y = q.popleft()
    for i in range(4):
        nx = x + xy[i][0]
        ny = y + xy[i][1]
        if 0 <= nx <= h-1 and 0 <= ny <= w-1 and ans[nx][ny] == -1:
            if ma[nx][ny] == ".":
                q.append((nx,ny))
                ans[nx][ny] = ans[x][y] + 1
        if nx == h-1 and ny == w-1:
            break
 
if ans[h-1][w-1] == -1:
    print(-1)
else:
    print(h*w - cou - ans[h-1][w-1])
### BUGGY CODE ###

from collections import*
(n,),*a=[list(map(int,t.split()))for t in open(0)]
d={}
s=0
es=[]
for i,b in enumerate(a):
    for j,k in zip(b,b[1:]):
        x,y=tuple(sorted((i,j-1))),tuple(sorted((i,k-1)))
        if not x in d:
            d[x]=s
            s+=1
        if not y in d:
            d[y]=s
            s+=1
        es+=(d[x],d[y]),
e=[[]for _ in range(s)]
for v1,v2 in es:e[v1]+=v2,
outs=defaultdict(list)
ins=defaultdict(int)
for v1,v2 in es:
    outs[v1].append(v2)
    ins[v2]+=1
q=deque(v1 for v1 in range(s)if ins[v1]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2]-=1
        if ins[v2]==0:
            q.append(v2)
if len(res)<s:
    print(-1)
    exit()
data=[1]*s
for i in res:
    t=data[i]+1
    for j in e[i]:
        if t>data[j]:data[j]=t
print(max(data))

### FIXED CODE ###

def main():
    from collections import defaultdict,deque
    from itertools import count
    (n,),*a=[list(map(int,t.split()))for t in open(0)]
    d=defaultdict(count().__next__)
    es=[]
    for i,b in enumerate(a,1):
        for j,k in zip(b,b[1:]):
            x,y=i,j
            if y<x:x,y=y,x
            v,w=i,k
            if w<v:v,w=w,v
            es+=(d[x*n+y],d[v*n+w]),
    s=len(d)
    outs=[[]for _ in range(s)]
    ins=[0]*s
    f=set(range(s))
    for i,j in es:
        outs[i]+=j,
        f-={j}
        ins[j]+=1
    q=deque(f)
    r=[]
    data=[0]*s
    m=0
    while q:
        i=q.popleft()
        r+=i,
        t=data[i]+1
        if t>m:m=t
        for j in outs[i]:
            ins[j]-=1
            if ins[j]<1:q+=j,
            if t>data[j]:data[j]=t
    print(-(len(r)<s)or m)
main()
### BUGGY CODE ###

# coding: utf-8

k = int(input())
queue = [1,2,3,4,5,6,7,8,9]

for i in range(k):
    a = queue.pop(0)
    if a % 10 != 0:
        queue.append(10 * a + (a%10) - 1)
    queue.append(10 * a + (a%10))
    if a % 10 != 9:
        queue.append(10 * a + (a%10) + 1)

print(a)

### FIXED CODE ###

# coding: utf-8
from collections import deque

k = int(input())
queue = deque([1,2,3,4,5,6,7,8,9])

for i in range(k):
    a = queue.popleft()
    if a % 10 != 0:
        queue.append(10 * a + (a%10) - 1)
    queue.append(10 * a + (a%10))
    if a % 10 != 9:
        queue.append(10 * a + (a%10) + 1)

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

s = input()
l = len(s)
idx = []
for i in range(l-1):
    if s[i] == ">" and s[i+1] == "<":
        idx.append(i+1)

idx = [0]+idx+[l]

L = []
cnt = 0
for i in range(len(idx)-1):
    L = s[idx[i]:idx[i+1]]

    for j in range(len(L)):
        a = L.count("<")
        b = L.count(">")
        k = max(a,b)
        r = min(a,b)
    if r >=1:
        cnt += k*(k+1)//2 + r*(r-1)//2
    else:
        cnt += k*(k+1)//2

print(cnt)

### FIXED CODE ###

s = input()
l = len(s)
idx = []
for i in range(l-1):
    if s[i] == ">" and s[i+1] == "<":
        idx.append(i+1)

idx = [0]+idx+[l]

L = []
cnt = 0
for i in range(len(idx)-1):
    L = s[idx[i]:idx[i+1]]

    for j in range(len(L)):
        a = L.count("<")
        b = L.count(">")
        k = max(a,b)
        r = min(a,b)
    if r >=1:
        cnt += k*(k+1)//2 + r*(r-1)//2
    else:
        cnt += k*(k+1)//2

print(cnt)
### BUGGY CODE ###

def main():
	n=int(input())
	a=list(map(int, input().split()))
	count = 0
	for i in range(n):
		for j in range(n):
			if i == j:
				count =count
			elif a[i]==a[j] :
				count+=1
				break
			else:
				count=count
	if count==0:
		print('YES')
	else:
		print('NO')
main()

### FIXED CODE ###

def main():
	n=int(input())
	a=list(map(int, input().split()))
	a.sort()
	c=0
	for i in range(n-1):
		if a[i] == a[i+1]:
			print('NO')
			c+=1
			break
	if c==0:
		print('YES')
main()
### BUGGY CODE ###

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

ans = 0
for i in range(len(S)):
    for j in range(i, len(S)):
        if (int(S[i:j+1])) % P == 0:
            ans += 1
    
print(ans)


### FIXED CODE ###

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

r_circ = []
v = 1
while True:
    r = v % P
    if r in r_circ:
        break
    r_circ.append(r)
    v *= 10

ans = 0
if P in (2, 5):
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i+1
else:
    pr = 0
    rcntmap = [0] * P
    rcntmap[0] = 1  # r - 0 patten
    for i in reversed(range(len(S))):
        d = int(S[i])
        r = (d * r_circ[(len(S)-1-i) % len(r_circ)] + pr) % P
        #r = int(S[i:]) % P
        ans += rcntmap[r]
    
        rcntmap[r] += 1
        pr = r

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

t = int(input())
A = [list(map(int, input().split())) for _ in range(t)]
for i in range(t):
    state = True
    a,b,c,d = A[i]
    keep = []
    keep.append(a)
    if a < b:
        state = False
    else:
        while True:
            if a < b:
                state = False
                break
            a -= b
            if a > c:
                if (a-c)%b:
                    a -= (((a-c)//b) + 1)*b
                    if a < 0:
                        state = False
                        break
                else:
                    a = c
            a += d
            if keep.count(a) >= 2:
                temp1 = keep.index(a)
                temp2 = keep[temp1+1:].index(a) + temp1+1
                if keep[temp1:temp2] == keep[temp2:]:
                    break
            keep.append(a)
    if state:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

from fractions import gcd
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    a,b,c,d = A[i]
    g = gcd(b,d)
    if a < b or b > d or b-g+(a%g)>c:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

# ARC60 D input
nw = list(map(int, input().split()))
N = nw[0]
w_limit = nw[1]

w = []
v = []
for i in range(N):
    wv = list(map(int, input().split()))
    w.append(wv[0])
    v.append(wv[1])

# ARC60 D recursive with memorization
dp = [{} for i in range(w_limit+1) for j in range(N+1)]
def rec_dp(i, j):
    if(j in dp[i]):
        return dp[i][j]
    
    res = 0
    if(i == N):
        res = 0
    elif(j < w[i]):
        res = rec_dp(i+1, j)
    else:
        res = max(rec_dp(i+1, j), rec_dp(i+1, j-w[i]) + v[i])
    
    dp[i][j] = res
    return res

print(rec_dp(0, w_limit))

### FIXED CODE ###

# ARC60 D input
nw = list(map(int, input().split()))
N = nw[0]
w_limit = nw[1]

w = []
v = []
for i in range(N):
    wv = list(map(int, input().split()))
    w.append(wv[0])
    v.append(wv[1])

# ARC60 D recursive with memorization
dp = [{} for j in range(N+1)]
def rec_dp(i, j):
    if(j in dp[i]):
        return dp[i][j]
    
    res = 0
    if(i == N):
        res = 0
    elif(j < w[i]):
        res = rec_dp(i+1, j)
    else:
        res = max(rec_dp(i+1, j), rec_dp(i+1, j-w[i]) + v[i])
    
    dp[i][j] = res
    return res

print(rec_dp(0, w_limit))
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def solve(i, j, shina):
    if i == len(shina):
        return 0

    if shina[i][0] > j:
        return solve(i + 1, j, shina)

    return max(solve(i + 1, j, shina), solve(i + 1, j - shina[i][0], shina) + shina[i][1])


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    ans = solve(0, W, shina)

    print(ans)

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

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

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

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


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

s = input()
origin = s
past = ''
cnt=0
while True:
    past = s
    s = s.replace('10','').replace('01','')
#    print(s)
#    print(past)
    if past==s:
        break

num = len(origin)-len(s)
print(num)

### FIXED CODE ###

s = input()
a = s.count('1')
b = s.count('0')

num = min(a,b)*2
print(num)
### BUGGY CODE ###

from itertools import permutations
import sys

N, M, R = map(int, sys.stdin.readline().split())
r = [int(i) - 1 for i in sys.stdin.readline().split()]
d = [[float('inf')] * N for j in range(N)]
for i in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    d[A-1][B-1] = min(d[A-1][B-1], C)
    d[B-1][A-1] = min(d[B-1][A-1], C)
for k in range(N):
    for s in range(N):
        for e in range(N):
            d[s][e] = min(d[s][e], d[s][k] + d[k][e])
l = True
for o in permutations(r):
    tmp_l = 0
    for s, e in zip(o[:-1], o[1:]):
        tmp_l = tmp_l + d[s][e]
    if l is True:
        l = tmp_l
    else:
        l = min(l, tmp_l)
print(l)

### FIXED CODE ###

from itertools import permutations
N, M, R = map(int, input().split())
r = [int(i) - 1 for i in input().split()]
d = [[10000000 for i in range(N)] for j in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    d[A-1][B-1] = min(d[A-1][B-1], C)
    d[B-1][A-1] = min(d[A-1][B-1], C)
for k in range(N):
    for s in range(N):
        for e in range(N):
            d[s][e] = min(d[s][e], d[s][k] + d[k][e])
l = True
for o in permutations(r):
    tmp_l = 0
    for s, e in zip(o[:-1], o[1:]):
        tmp_l = tmp_l + d[s][e]
    if l is True:
        l = tmp_l
    else:
        l = min(l, tmp_l)
print(l)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
def main():
	R, G, B, N = map(int, input().split(" "))
	
	ans = 0
	for i in range(N+1):
		r = i * R
		for j in range(N+1):
			g = j * G
			if N - r - g < 0:
				continue
			if (N - r - g) % B != 0:
				continue
			k = (N - r - g) // B
			#print("{} {} {}".format(i, j, k))
			ans += 1
			

	print(ans)

	
	
if __name__ == "__main__":
	main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
def main():
	R, G, B, N = map(int, input().split(" "))
	
	ans = 0
	for i in range(N+1):
		r = i * R
		for j in range(N+1):
			g = j * G
			if N - r - g < 0:
				continue
			if (N - r - g) % B != 0:
				continue
			#k = (N - r - g) // B
			#print("{} {} {}".format(i, j, k))
			ans += 1
			

	print(ans)

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

import numpy as np

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

A_matrix = []
for i in range(N):
    m = [0] * N
    if i != N - 1:
        m[i] = m[i+1] = 0.5
    else:
        m[i] = m[0] = 0.5
    A_matrix.append(m)

A_matrix = np.array(A_matrix)
A = A.T
A_inv = np.linalg.inv(A_matrix)
ans = np.dot(A_inv, A)
ans = ans.astype(int)
print(" ".join(str(n) for n in ans))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
X = [0] * N
X[0] = sum(A) - 2*(sum(A[1::2]))
for i in range(1, N):
    X[i] = 2*A[i-1] - X[i-1]
print(' '.join(str(x) for x in X))
### BUGGY CODE ###

n=int(input())
li=list(map(int,input().split()))
ans=0

for i in range(n):
    for j in range(i+1):
        if li[i]>li[j]:
            ans+=1
            break

print(n-ans)

### FIXED CODE ###

n=int(input())
li=list(map(int,input().split()))
ans=0
tmp=li[0]

for i in range(n):
    if li[i]>tmp:
        ans+=1
    else:
        tmp=li[i]

print(n-ans)
### BUGGY CODE ###

INF = 10**18

def solve(N, Ma, Mb, sol):
    if N % 2 == 1:
        sol.append((0, 0, 0))
        N += 1

    M = N // 2

    sol1 = sol[:M]
    sol2 = sol[M:]

    S1 = []
    S2 = []

    for i in range(2**M):
        A1, B1, C1 = 0, 0, 0
        A2, B2, C2 = 0, 0, 0
        for j in range(M):
            if (i >> j) & 1:
                a1, b1, c1 = sol1[j]
                a2, b2, c2 = sol2[j]
                A1 += a1
                B1 += b1
                C1 += c1
                A2 += a2
                B2 += b2
                C2 += c2
        S1.append((A1, B1, C1))
        S2.append((A2, B2, C2))

    D = dict()
    S2.sort(key=lambda x: x[2], reverse=True)

    res = INF

    for i in range(2**M):
        a, b, c = S2[i]
        x = Mb * a - Ma * b
        if x == 0 and c > 0:
            res = min(res, c)
        if not x in D or c > 0:
            D[x] = c

    for i in range(2**M):
        a, b, c = S1[i]
        x = Ma * b - Mb * a
        if x == 0 and c > 0:
            res = min(res, c)
        if x in D and D[x] + c > 0:
            res = min(res, D[x] + c)

    return res

N, Ma, Mb = map(int, input().split())
sol = [tuple(map(int, input().split())) for _ in range(N)]

res = solve(N, Ma, Mb, sol)

print(res if res != INF else -1)

### FIXED CODE ###

INF = 10**18

def solve(N, Ma, Mb, sol):
    if N % 2 == 1:
        sol.append((0, 0, 0))
        N += 1

    M = N // 2

    sol1 = sol[:M]
    sol2 = sol[M:]

    S1 = []
    D = dict()
    res = INF

    for i in range(2**M):
        A1, B1, C1 = 0, 0, 0
        A2, B2, C2 = 0, 0, 0
        for j in range(M):
            if (i >> j) & 1:
                a1, b1, c1 = sol1[j]
                a2, b2, c2 = sol2[j]
                A1 += a1
                B1 += b1
                C1 += c1
                A2 += a2
                B2 += b2
                C2 += c2
        S1.append((A1, B1, C1))
        x = Mb * A2 - Ma * B2
        if x == 0 and C2 > 0:
            res = min(res, C2)
        if not x in D or 0 < C2 < D[x]:
            D[x] = C2

    for i in range(2**M):
        a, b, c = S1[i]
        x = Ma * b - Mb * a
        if x == 0 and c > 0:
            res = min(res, c)
        if x in D and D[x] + c > 0:
            res = min(res, D[x] + c)

    return res

N, Ma, Mb = map(int, input().split())
sol = [tuple(map(int, input().split())) for _ in range(N)]

res = solve(N, Ma, Mb, sol)

print(res if res != INF else -1)
### BUGGY CODE ###

from collections import Counter

n = int(input())
s = []
for _ in range(n):
    s.append(Counter(input()))

i, ans=0, 0
flag=[-1]*n

while i<n:
    if flag[i] == 1:
        i+=1
        continue
    flag[i] = 1
    tmp = 1
    for j in range(i+1, n):
        if s[i] == s[j]:
            flag[j] = 1
            tmp+=1
    ans+=(tmp*(tmp-1)//2)
    i+=1

print(ans)




### FIXED CODE ###

from collections import Counter

n = int(input())
s={}

for _ in range(n):
    ss = str(sorted(input()))
    if ss not in s:
        s[ss] = 1
    else:
        s[ss] += 1

ans=0
for c in s.values():
    ans += (c*(c-1)//2)
print(ans)
### BUGGY CODE ###

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

if min(A) == 0:
    ans = 0
    print(ans)
    exit()
else:
    for i in A:
        ans *= i
    if ans > 10**18:
        ans = -1
        print(ans)
        exit()

print(ans)

### FIXED CODE ###

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

if min(A) == 0:
    print(0)
    exit()

for i in A:
    ans *= i
    if ans > 10**18:
        print(-1)
        exit()

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

def main():
    N = int(input())
    A = [int(value) for value in input().split(" ")]
    result = 1
    for value in A:
        result *= value
        if 0 in A:
            print(0)
            exit()
        if result>10**18:
            print(-1)
            exit()
    
    print(result)


if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = sorted([int(value) for value in input().split(" ")], reverse=True)
    result = 1
    if 0 in A:
        print(0)
        exit()
    for value in A:
        result *= value
        if result>10**18:
            print(-1)
            exit()
    
    print(result)


if __name__=="__main__":
    main()