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

N = int(input())
XL = [list(map(int, input().split())) for _ in range(N)]

X = [XL[i][0] for i in range(N)]
L = [XL[i][1] for i in range(N)]

# ぶつかるものを挙げる
def hit(x_ids, in_x_id):
    ans = []
    for i in x_ids:
        # print(X[in_x_id] - L[in_x_id], X[i] + L[i], X[i] - L[i], X[in_x_id] + L[in_x_id])
        if X[in_x_id] - L[in_x_id] < X[i] + L[i] and X[i] - L[i] < X[in_x_id] + L[in_x_id]:
            # print('haitta')
            ans.append(i)
    return ans


# n番目までの入れ方全パターン
dp = [[] for _ in range(N)]
dp[0].append([0])

for i in range(1, N):
# i-1番目まで見たときの最大個数のパターンに
    for j in dp[i-1]:
# i番目のを追加してもぶつからなければ追加
        hitlist = hit(j, i)
        # print('i, j:', i, j)
        # print(hitlist)
        if len(hitlist) == 0:
            dp[i].append(j+[i])
        else:
# ぶつかるなら、i番目を入れないパターンがある
            dp[i].append(j)
# i番目とぶつかるやつが1個ならそれを消してn番目を入れるパターンもある
            if len(hitlist) == 1:
                dp[i].append(j[: hitlist[0]] + j[hitlist[0] :] + [i])

print(len(dp[-1][0]))


### FIXED CODE ###

N = int(input())
XL = [list(map(int, input().split())) for _ in range(N)]

XL = sorted(XL, key=lambda x: x[0]+x[1])

ans = 1
right = XL[0][0] + XL[0][1]

for i in range(1, N):
    if right <= XL[i][0] - XL[i][1]:
        right = XL[i][0] + XL[i][1]
        ans += 1

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

#Make a Rectangle
N = int(input())
A = list(map(int, input().split()))

a = sorted(list(set(A)), reverse=True)
b = []
for ai in a:
    c = A.count(ai)
    b += [ai]*(c//2)
    if (len(b)>=4):
        break
if (len(b)<2):
    print(0)
else:
    print(b[0]*b[1])

### FIXED CODE ###

#Make a Rectangle
N = int(input())
A = list(map(int, input().split()))

a = sorted(A, reverse=True)
b = []

i = 0
while i<N-1:
    if ( a[i]==a[i+1] ):
        b+=[a[i]]
        i+=2
    else:
        i+=1
    if (len(b)>1):
        break

if (len(b)<2):
    print(0)
else:
    print(b[0]*b[1])
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


N = INT()
e = [[] for _ in range(N)]

for _ in range(N-1):
    t = LIST()
    e[t[0]-1].append([t[1]-1, t[2]%2])
    e[t[1]-1].append([t[0]-1, t[2]%2])

a = [0] * N
f = []

"""
for edge in G:
    if edge[2]%2 == 1:
        a[edge[1]-1] = 1 - a[edge[0]-1]
    else:
        a[edge[1]-1] = a[edge[0]-1]
"""
def r(n):
    f.append(n)
    for nn in e[n]:
        if nn[0] not in f:
            if nn[1] == 0:
                a[nn[0]] = a[n]
                r(nn[0])
            else:
                a[nn[0]] = 1 - a[n]
                r(nn[0])

r(0)
for item in a:
    print(item)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


N = INT()
e = [[] for _ in range(N)]

for _ in range(N-1):
    t = LIST()
    e[t[0]-1].append([t[1]-1, t[2]%2])
    e[t[1]-1].append([t[0]-1, t[2]%2])

a = [0] * N
f = [0] * N

"""
for edge in G:
    if edge[2]%2 == 1:
        a[edge[1]-1] = 1 - a[edge[0]-1]
    else:
        a[edge[1]-1] = a[edge[0]-1]
"""
def r(n):
    f[n] = 1
    for nn in e[n]:
        if f[nn[0]] == 0:
            if nn[1] == 0:
                a[nn[0]] = a[n]
                r(nn[0])
            else:
                a[nn[0]] = 1 - a[n]
                r(nn[0])

r(0)
for item in a:
    print(item)
### BUGGY CODE ###

import math
from math import floor
A,B,N = map(int,input().split())
maxi = 0
Npower = 0
diff = 0
S = N
while S/10 >= 1:
    Npower += 1
    S /=10
if Npower >= 8: 
    for i in range(0,1000000):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi,0)
    for i in range(N-10**7,N+1):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi,0)
else:
    for i in range(0,N+1):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi,0)
print(maxi)

### FIXED CODE ###

import math
from math import floor
A,B,N = map(int,input().split())
def f(x):
  return floor(A*x/B) - A*floor(x/B)
print(f(min(B-1,N)))
### BUGGY CODE ###

N = int(input())
s = [None]*N
for i in range(N):
    s[i] = sorted(input())

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if s[i] == s[j]:
            ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
anagram = {}

ans = 0
for i in range(N):
    tmp = str(sorted(input()))
    if tmp in anagram:
        ans += anagram[tmp]
        anagram[tmp] += 1
    else:
        anagram[tmp] = 1

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

import sys,math
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202007_2nd/C_input.txt")
else:
    f=sys.stdin
# Find the number of triples of integers (x,y,z) such that
# (x+y)**2 + (y+z)**2 + (x+z)**2 = 2*N
N=int(f.readline().strip())
for _ in range(N):
    A=(_+1)*2
    I=int(math.sqrt(A))
    cnt=0
    for __ in range(I):
        for ___ in range(I):
            for ____ in range(I):
                if ((__+___+2)**2)+((___+____+2)**2)+((__+____+2)**2)==A:
                    cnt+=1
    print(cnt)

### FIXED CODE ###

import sys,math
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202007_2nd/C_input.txt")
else:
    f=sys.stdin
# Find the number of triples of integers (x,y,z) such that
# (x+y)**2 + (y+z)**2 + (x+z)**2 = 2*N
N=int(f.readline().strip())
ans=[0 for _ in range(N)]
I=int(math.sqrt(N))
for __ in range(I):
    A2=N-((__+1)**2)
    if A2<=0:
        break
    I2=int(math.sqrt(A2))
    for ___ in range(I2):
        A3=A2-((___+1)**2)
        if A3<=0:
            break
        I3=int(math.sqrt(A3))
        for ____ in range(I3):
            tmp=((__+___+2)**2)+((___+____+2)**2)+((__+____+2)**2)
            if tmp<=2*N:
                ans[int(tmp/2)-1]+=1
            else:
                break
for _ in range(N):
    print(ans[_])
f.close()
### BUGGY CODE ###

import bisect
N=int(input())
ue=list(map(int,input().split()))
naka=list(map(int,input().split()))
sita=list(map(int,input().split()))
ue.sort(),sita.sort(),naka.sort()
count=0
stop=[N]*N
for i in range(N):
    k=naka[i]
    stop_index=bisect.bisect_right(sita,k)
    if stop_index!=N:
        stop[i]=N-stop_index
for i in range(N):
    k=ue[i]
    a=bisect.bisect_right(naka,k)
    if a!=N:
        for j in range(a,N):
            count+=stop[j]
print(count)


### FIXED CODE ###

import bisect
N=int(input())
ue=list(map(int,input().split()))
naka=list(map(int,input().split()))
sita=list(map(int,input().split()))
sita.sort(),naka.sort(),ue.sort()
count2=[0]*N
count1=[0]*N
for i in range(N):
    m = naka[i]
    k=naka[i]
    small=bisect.bisect_left(ue,k)
    count1[i]=small
    big = bisect.bisect_right(sita, m)
    count2[i]=N-big
ans=0
for i in range(N):
    ans+=count1[i]*count2[i]
print(ans)
### BUGGY CODE ###

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

tree = [set([i]) for i in range(N+1)]
points = [0] * N

for i in range(1, N):
  a, b = map(int, input().split())
  tree[a].add(b)
  for j in range(a):
    if a in tree[j]:
      tree[j].add(b)  

for i in range(Q):
  p, x = map(int, input().split())
  for node in tree[p]:
    points[node-1] += x
    
for point in points:
  print(point, end=" ")

### FIXED CODE ###

n,q = map(int,input().split())
rl = [0] * n
scores = [0] * n
for i in range(n-1):
    a,b = map(int,input().split())
    rl[b-1] = a-1
for j in range(q):
    p,x = map(int,input().split())
    scores[p-1] += x
for k in range(1,n):
    scores[k] += scores[rl[k]]
print(*scores)
### BUGGY CODE ###

# encoding:utf-8
def main():
	N, K = list(map(int, input().split()))
	nums = list(map(int, input().split()))

	max_num = max(nums)
	min_num = min(nums)

	# 最大値が越えてたらだめ
	if K > max_num:
		return("IMPOSSIBLE")

	decomp_min = decomp(min_num)

	for i, x in enumerate(decomp_min):
		res = [y % x for y in nums]

		# 共通因子を持ってなかったらだめ
		if max(res) == min(res):
			if K % x > 0:
				return("IMPOSSIBLE")
	else:
		return("POSSIBLE")

def decomp(n):
	i = 2
	table = [n]

	while i * n  <= n * n:
		if n % i == 0:
			table.append(int(i))
		i += 1
	return(table)

if __name__ == '__main__':
	print(main())

### FIXED CODE ###

import functools as ft

def gcd(a,b):
    while b > 0:
        a, b = b, a % b
    return a

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

	max_num = max(nums)
	g = ft.reduce(lambda x, y: gcd(x, y), nums)

	if K <= max_num and K % g == 0:
		print("POSSIBLE")
	else:
		print("IMPOSSIBLE")

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

def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b
import sys
sys.setrecursionlimit(1000000)
from collections import deque

n, m = getMN()

parents = [[] for i in range(n+1)]
childs = [[] for i in range(n+1)]

k = m-1+n
for i in range(k):
    p1,p2 = getMN()
    parents[p2].append(p1)
    childs[p1].append(p2)

dst = [0 for i in range(n+1)]

d = deque()
n_root = 0
for i, x in enumerate(parents[1:]):
    if not x:
        n_root = i+1
        break

def bfs(n_cur):
    for c in childs[n_cur]:
        d.append(c)
        dst[c] = max(dst[c], dst[n_cur]+1)
    while(d):
        bfs(d.pop())

bfs(n_root)

for plist in parents[1:]:
    if plist:
        cur = -1
        ans = plist[0]
        for p in plist:
            if dst[p] > cur:
                cur = dst[p]
                ans = p
        print(ans)
    else:
        print(0)


### FIXED CODE ###

def getN():
    return int(input())


def getNM():
    return map(int, input().split())


def getList():
    return list(map(int, input().split()))

n,m = getNM()
children = [[] for i in range(n+2)]
n_in = [0] * (n+1)
par_origin = [0] * (n+1)

#入力の処理
for i in range(n+m-1):
    a,b = getNM()
    children[a].append(b)
    n_in[b] += 1

#根を見つける
for i in range(1,n+m-1):
    if n_in[i]:
        pass
    else:
        root = i
        break

#次数を減らしながら探索
import queue
def bfs(root):
    q = queue.Queue()
    q.put(root)
    while(True):
        try:
            cur = q.get(block=False)
        except:
            break
        for c in children[cur]:
            if n_in[c] == 1:
                par_origin[c] = cur
                q.put(c)
            else:
                n_in[c] -= 1

bfs(root)
for i in range(1, n+1):
    print(par_origin[i])
### BUGGY CODE ###

N=int(input())
member=[0]+list(map(int,input().split()))
max=max(member)
member=list(map(str,member))
answer=""
for i in range(max+1):
    answer=answer+str(member.count(str(i+1)))+"\n"
answer=answer+"0\n"*(N-max-1)
print(answer[:-1])


### FIXED CODE ###

a=[0]*int(input())
for i in input().split():a[int(i)-1]+=1
print(*a)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b
def ceil(x):
    return math.ceil(x)
def floor(x):
    return math.floor(x)

def main():
    mod = 998244353
    N, K = map(int, input().split())
    L = [0] * K
    R = [0] * K
    for i in range(K):
        L[i], R[i] = map(int, input().split())

    S = set()
    for i in range(K):
        for j in range(L[i], R[i] + 1):
            S.add(j)

    dp = [0] * N
    dp[0] = 1
    for i in range(1, N):
        for s in S:
            if i - s >= 0:
                dp[i] += dp[i - s] % mod
    print(dp[N - 1] % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b
def ceil(x):
    return math.ceil(x)
def floor(x):
    return math.floor(x)


def main():
    MOD = 998244353
    N, K = map(int, input().split())
    L = [0] * K
    R = [0] * K
    for i in range(K):
        L[i], R[i] = map(int, input().split())

    dp = [0] * (N + 1)
    dpsum = [0] * (N + 1)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, N + 1):
        for j in range(K):
            li = i - R[j]
            li = max(li, 1)
            ri = i - L[j]
            if ri < 0:
                continue
            dp[i] += (dpsum[ri] - dpsum[li - 1]) % MOD
        dpsum[i] += (dpsum[i - 1] + dp[i]) % MOD
    print(dp[N] % MOD)


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

n, q = map(int, input().split())

AB = [[int(x) for x in input().split()] for _ in range(n - 1)]
PX = [[int(x) for x in input().split()] for _ in range(q)]

graph = [[] for _ in range(n + 1)]
# 各ノードと連結するノードを要素に持つ配列
# e.g., graph[1] -> ノード１と連結するノードを要素に持つ
for a, b in AB:
	graph[a].append(b)
	graph[b].append(a)

# 根に点数を入れる
value = [0] * (n + 1)
for p, x in PX:
	value[p] += x

# 根から値を流す
q = [(1, 0)]
while q:
	x, parent = q.pop() # (1, 0)
	value[x] += value[parent]
	# 連結する成分について繰り返す
	# このとき、親のノードに流さないように注意
	# ここでの操作は、自分の子のノードを加えること
	for y in graph[x]:
		if y == parent:
			continue
		q.append((y, x)) #(親,子)

res = ' '.join(map(str, value[1:]))
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, q = map(int, input().split())

AB = [[int(x) for x in input().split()] for _ in range(n - 1)]
PX = [[int(x) for x in input().split()] for _ in range(q)]

graph = [[] for _ in range(n + 1)]
# 各ノードと連結するノードを要素に持つ配列
# e.g., graph[1] -> ノード１と連結するノードを要素に持つ
for a, b in AB:
	graph[a].append(b)
	graph[b].append(a)

# 根に点数を入れる
value = [0] * (n + 1)
for p, x in PX:
	value[p] += x

# 根から値を流す
q = [(1, 0)]
while q:
	x, parent = q.pop() # (1, 0)
	value[x] += value[parent]
	# 連結する成分について繰り返す
	# このとき、親のノードに流さないように注意
	# ここでの操作は、自分の子のノードを加えること
	for y in graph[x]:
		if y == parent:
			continue
		q.append((y, x)) #(親,子)

res = ' '.join(map(str, value[1:]))
print(res)
### BUGGY CODE ###

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

dp = [0] * n

for i in range(1, n):
  dp[i] = min(dp[j] + abs(h[j]-h[i]) for j in range(max(i-k, 0), i))

print(dp[n-1])

### FIXED CODE ###

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

dp = [0] * n

for i in range(1, n):
  s = max(i-k, 0)
  dp[i] = min(dp[j] + abs(h[j]-h[i]) for j in range(s, i))

print(dp[n-1])
### BUGGY CODE ###

import sys
n=int(input())
xyh=[list(map(int,input().split())) for i in range(n)]
x = [xyh[i][0] for i in range(n)]
y = [xyh[i][1] for i in range(n)]
h = [xyh[i][2] for i in range(n)]
ch=max(h)
while ch<=10000000000:
  for cx in range(101):
    for cy in range(101):
      flg=0
      for i in range(n):
        if abs(x[i]-cx)+abs(y[i]-cy)!=ch-h[i]:
          flg=1
          break
      if flg==0:
        print(cx,cy,ch)
        sys.exit()
  ch+=1

### FIXED CODE ###

import sys
n=int(input())
xyh=[list(map(int,input().split())) for i in range(n)]
xyh.sort(key=lambda x:x[2],reverse=True)
if xyh[0][2]==0:
  total=0
  for i in range(n):
    total+=xyh[i][0]
  cx=total//n
  total=0
  for i in range(n):
    total+=xyh[i][1]
  cy=total//n
  ch=abs(xyh[0][0]-cx)+abs(xyh[0][1]-cy)
  print(cx,cy,ch)
  sys.exit()  
for cx in range(101):
  for cy in range(101):
    ch=abs(xyh[0][0]-cx)+abs(xyh[0][1]-cy)+xyh[0][2]
    flg=0
    for i in range(n):
      if xyh[i][2]!=max(0, ch-abs(xyh[i][0]-cx)-abs(xyh[i][1]-cy)):
        flg=1
        break
    if flg==0:
      print(cx,cy,ch)
      sys.exit()
### BUGGY CODE ###

from numpy.linalg import solve
N=int(input())
A=input().split()
for i in range(N):
    A[i]=2*int(A[i])
x=[None]*N
for i in range(N-1):
    x[i]=[0]*N
    x[i][i],x[i][i+1]=1,1
x[N-1]=[0]*N
x[N-1][0],x[N-1][N-1]=1,1
y=solve(x,A)
for i in range(N):
    print(int(y[i]),end=' ')


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
A=list(map(int,input().split()))
y=0
for i in range(N-1):
    y=2*(A[i]-y//2)
l=[None]*N
l[0]=(2*A[-1]-y)//2
for i in range(1,N):
    l[i]=2*(A[i-1]-l[i-1]//2)
print(*l)
### BUGGY CODE ###

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()))

E=[]
for i in range(X):
  for j in range(Y):
    E.append(A[i]+B[j])

C.sort(reverse=True)
E.sort(reverse=True)
ans=[]
for i in range(min(K,len(E))):
  for j in range(Z):
    ans.append(E[i]+C[j])
ans.sort(reverse=True)

for i in range(K):
  print(ans[i])

### FIXED CODE ###

import heapq

def main():
  X,Y,Z,K=map(int,input().split())
  A=list(reversed(sorted(map(int,input().split()))))
  B=list(reversed(sorted(map(int,input().split()))))
  C=list(reversed(sorted(map(int,input().split()))))
  q=[(-A[0]-B[0]-C[0],0,0,0)]
  queued={(0,0,0)}
  for i in range(K):
    v,s,t,u=heapq.heappop(q)
    print(-v)
    for e,f,g in [(s,t,u+1),(s,t+1,u),(s+1,t,u)]:
      if e>=X or f>=Y or g>=Z:
        continue
      if (e,f,g) in queued:
        continue
      heapq.heappush(q,(-(A[e]+B[f]+C[g]),e,f,g))
      queued.add((e,f,g))
      
if __name__=="__main__":
  main()
### BUGGY CODE ###

import fractions
n = int(input())
a = list(map(int, input().split()))
l = a[0]
for i in range(1, n): l = l // fractions.gcd(l, a[i]) * a[i]
print(sum([l // a[i] for i in range(n)]) % 1000000007)


### FIXED CODE ###

import fractions
n = int(input())
a = list(map(int, input().split()))
l = a[0]
for i in range(1, n): l = l // fractions.gcd(l, a[i]) * a[i]
s = 0
for i in range(n): s += l // a[i]
print(s % 1000000007)
### BUGGY CODE ###

from bisect import bisect_right

n, d, a = map(int, input().split())
m = []
x_list = []
for _ in range(n):
    x, h = map(int, input().split())
    m.append([x, (h+a-1)//a])
    x_list.append(x)
m.sort()
x_list.sort()

pos = m[0][0]
idx_start = 0
res = 0
while True:
    idx_end = bisect_right(x_list, pos+2*d) - 1
    for i in range(idx_start+1, idx_end+1):
        m[i][1] -= m[idx_start][1]
    res += m[idx_start][1]
    m[idx_start][1] = 0
    while idx_start < n and m[idx_start][1] <= 0:
        idx_start += 1
    if idx_start >= n:
        break
    pos = m[idx_start][0]

print(res)

### FIXED CODE ###

from math import ceil
from collections import deque
N, D, A = map(int, input().split())
Monsters = sorted([list(map(int, input().split())) for i in range(N)])
Monsters = [[x, ceil(h / A)] for x, h in Monsters]


acc_damage = 0
que = deque([])

ans = 0
for x, h in Monsters:
    while que and x > que[0][0]:
        limit, damage = que.popleft()
        acc_damage -= damage

    need = max(0, h - acc_damage)
    ans += need
    acc_damage += need

    if need:
        que.append([x + 2 * D, need])

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

N,M = (int(x) for x in input().split())
P,Y=[],[]
ID = [0 for i in range(M)]
for i in range(M):
    p,y = (int(x) for x in input().split())
    P.append(p)
    Y.append(y)

Ys = sorted(Y)
num = [1 for i in range(N)]

for i in range(M):
    ind = Y.index(Ys[i])
    Pi = P[ind]
    ID[ind] = str(Pi).zfill(6) + str(num[Pi-1]).zfill(6)
    num[Pi-1] += 1

for i in range(M):
    print(ID[i])

### FIXED CODE ###

N,M = map(int, input().split())
city, ID = [[] for _ in range(N+1)], [0 for _ in range(M)]
for i in range(M):
    P, Y = map(int, input().split())
    city[P].append([Y,i])
for i in range(1, N+1):
    city[i].sort()
    for j in range(len(city[i])):
        ID[city[i][j][1]] = str(i).zfill(6) + str(j+1).zfill(6)
for x in ID:    print(x)
### BUGGY CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# Ma:Mbを満たす量を全探索する
# 量を決めたときの最小予算は半分全列挙から分かる

from itertools import product

N,Ma,Mb = LI()
a,b,c = LIR(N,3)

Z1 = list(product([0,1],repeat=N//2))
Z2 = list(product([0,1],repeat=N-N//2))

d1 = defaultdict(list)
d2 = defaultdict(list)

for z in Z1:
    val_a = 0
    val_b = 0
    cost = 0
    for i,z0 in enumerate(z):
        if z0:
            val_a += a[i]
            val_b += b[i]
            cost += c[i]
    d1[(val_a,val_b)].append(cost)

for k in d1.keys():
    d1[k].sort()

for z in Z2:
    val_a = 0
    val_b = 0
    cost = 0
    for i,z0 in enumerate(z):
        if z0:
            val_a += a[N//2+i]
            val_b += b[N//2+i]
            cost += c[N//2+i]
    d2[(val_a,val_b)].append(cost)

for k in d2.keys():
    d2[k].sort()

vals = []
now = 1
while True:
    if Ma*now <= sum(a) and Mb*now <= sum(b):
        vals.append((Ma*now,Mb*now))
        now += 1
    else:
        break

ans = float('inf')
for v in vals:
    for k in d1.keys():
        left_a = v[0]-k[0]
        left_b = v[1]-k[1]
        if d2[(left_a,left_b)]:
            if d1[k][0]+d2[(left_a,left_b)][0] < ans:
                ans = d1[k][0]+d2[(left_a,left_b)][0]

if ans == float('inf'):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,Ma,Mb = LI()
a,b,c = LIR(N,3)

amax = sum(a)
bmax = sum(b)

# dp[i][j][k]: 薬品iまで見て，Aがjグラム，Bがkグラムの最小予算
dp = [[[5000]*(bmax+1) for _ in range(amax+1)] for _ in range(N)]
dp[0][a[0]][b[0]] = c[0]
dp[0][0][0] = 0
for i in range(1,N):
    for j in range(amax+1):
        for k in range(bmax+1):
            if j == k == 0:
                dp[i][j][k] = 0
            elif j-a[i] < 0 or k-b[i] < 0:
                dp[i][j][k] = dp[i-1][j][k]
            else:
                dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][j-a[i]][k-b[i]]+c[i])

ans = 5000
now = 1
while True:
    if Ma*now <= amax and Mb*now <= bmax:
        if dp[N-1][Ma*now][Mb*now] < ans:
            ans = dp[N-1][Ma*now][Mb*now]
        now += 1
    else:
        break

if ans == 5000:
    print('-1')
else:
    print(ans)
### BUGGY CODE ###

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

ans = 1
for i in A:
  if any(j == 0 for j in A) == True:
    ans = 0
    break
  ans *= i
  if ans > 10**18:
    ans = -1
    break

print(ans)

### FIXED CODE ###

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

ans = 1

if 0 in A:
  ans = 0
else:
  for i in range(N):
    ans *= A[i]
    i += 1
    if ans > 10**18:
      ans = -1
      break

print(ans)