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

import sys
import functools


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


@functools.lru_cache(maxsize=None)
def solve(h):
    if h <= 0:
        return 0

    ret_val = float("inf")
    for a, b in AB:
        ret_val = min(ret_val, b + solve(h - a))
    return ret_val


sys.setrecursionlimit(100000)

H, N = inpl()
AB = [inpl() for i in range(N)]
AB.sort(key=lambda ab: (ab[0] / ab[1], -ab[0]), reverse=True)
# print(AB)
print(solve(H))


### FIXED CODE ###

import sys
import functools


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


@functools.lru_cache(maxsize=None)
def solve(h):
    if h <= 0:
        return 0

    ret_val = float("inf")
    for a, b in AB:
        val = b + solve(h - a)
        if val < ret_val:
            ret_val = val
        else:
            break
    return ret_val


sys.setrecursionlimit(100000)

H, N = inpl()
AB = [inpl() for i in range(N)]
AB.sort(key=lambda ab: (ab[0] / ab[1], -ab[0]), reverse=True)
# print(AB)
print(solve(H))
### BUGGY CODE ###

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

ans = 0
for l in range(N-1):
    for r in range(l+2, N):
        if A[l] > N-l:
            break
        if r-l == A[l] + A[r]:
            ans += 1

print(ans)

### FIXED CODE ###

import collections

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

L = [i+j for i, j in enumerate(A)]
R = [i-j for i, j in enumerate(A)]

l = collections.Counter(L)
r = collections.Counter(R)

ans = 0
for i in l.keys():
    ans += l[i]*r[i]

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

import heapq

class PriorytyQueue(object):

    def __init__(self, arr, target='min'):
        self.arr = arr
        self.target = target
        self._heapify()
    
    def _heapify(self):
        if self.target == 'max':
            self.arr = list(map(lambda x:x*(-1), self.arr))
        heapq.heapify(self.arr)
    
    def push(self, x):
        if self.target == 'max':
            x *= -1
        heapq.heappush(self.arr, x)

    def pop(self):
        res = heapq.heappop(self.arr)
        if self.target == 'max':
            return res*(-1)
        else:
            return res
    
    def get_arr(self):
        if self.target == 'max':
            return list(map(lambda x:x*(-1), self.arr))
        else:
            return self.arr
    
    def is_empty(self):
        return len(self.arr) == 0

# ------------------------------------------ #
from collections import defaultdict

N, M = map(int, input().split())
jobs = defaultdict(list)
for i in range(N):
    a, b = map(int, input().split())
    if a > M:
        continue
    jobs[a].append(b)

if __name__ == "__main__":

    ans = 0
    pq = PriorytyQueue([], target='max')
    # d: 残りの日数(d日以上の仕事なら可能)
    for d in range(1, M+1):
        if d in jobs.keys():
            moneys = jobs[d]
            for money in moneys:
                pq.push(money)
        if len(pq.get_arr()) != 0:
            ans += pq.pop()
    print(ans)

### FIXED CODE ###

import heapq
from collections import defaultdict

class PriorytyQueue(object):

    def __init__(self, arr, target='min'):
        self.arr = arr
        self.target = target
        self._heapify()
    
    def _heapify(self):
        if self.target == 'max':
            self.arr = list(map(lambda x:x*(-1), self.arr))
        heapq.heapify(self.arr)
    
    def push(self, x):
        if self.target == 'max':
            x *= -1
        heapq.heappush(self.arr, x)

    def pop(self):
        res = heapq.heappop(self.arr)
        if self.target == 'max':
            return res*(-1)
        else:
            return res
    
    def get_arr(self):
        if self.target == 'max':
            return list(map(lambda x:x*(-1), self.arr))
        else:
            return self.arr
    
    def is_empty(self):
        return len(self.arr) == 0

n, m = map(int, input().split())
jobs = defaultdict(list)
for _ in range(n):
    a, b = map(int, input().split())
    if a > m:
        continue
    jobs[a].append(b)

res = 0
candidates = PriorytyQueue(arr=[],
                           target='max')
for d in range(1, m+1):
    if d in jobs.keys():
        for m in jobs[d]:
            candidates.push(m)
    if not(candidates.is_empty()):
        res += candidates.pop()
print(res)
### BUGGY CODE ###

import itertools
N,M,R=map(int, input().split())
r=list(map(int, input().split()))
G = [[float("inf")]*N for i in range(N)] 
for i in range(M):
    a,b,c=map(int, input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c

def warshall_floyd(G):
    #d[i][j]: iからjへの最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                G[i][j] = min(G[i][j],G[i][k] + G[k][j])
    return G
G=warshall_floyd(G)
ans=10**8
for L in itertools.permutations(r):
    L=list(L)
    sub=0
    for i in range(1,R):
        s=L[i-1]
        t=L[i]
        sub+=G[s-1][t-1]
    ans=min(ans, sub)
print(ans)

### FIXED CODE ###

import itertools
N,M,R=map(int, input().split())
r=list(map(int, input().split()))
G = [[float("inf")]*N for i in range(N)] 
for i in range(M):
    a,b,c=map(int, input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c

def warshall_floyd(G):
    #d[i][j]: iからjへの最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                G[i][j] = min(G[i][j],G[i][k] + G[k][j])
    return G
G=warshall_floyd(G)
ans=10**8
for L in itertools.permutations(r):
    L=list(L)
    sub=0
    for i in range(1,R):
        s=L[i-1]
        t=L[i]
        sub+=G[s-1][t-1]
    ans=min(ans, sub)
print(ans)
### BUGGY CODE ###

s = input()
t = 0
number = 0
m = [0 for i in range(2019)]
m[0] = 1
for i in range(len(s)):
    t = t  +  int(s[len(s) - 1 - i])* (10**i)
    #print(t)
    m[t % 2019] += 1
    #print(t%2019)

for j in range(2019):
    if m[j]>= 2:
        number += (m[j]*(m[j] - 1))//2

print(number)

### FIXED CODE ###

s = input()
t = 0
number = 0
#m = [0 for i in range(2019)]
m = [0]*2019
m[0] = 1
a = 1
for i in range(len(s)):
    t = t  +  int(s[len(s) - 1 - i])* a 
    #print(t)
    m[t % 2019] += 1
    a = a * 10
    a = a % 2019
    #print(t%2019)

for j in range(2019):
    #if m[j]>= 2:
    number += (m[j]*(m[j] - 1))//2

print(number)
### BUGGY CODE ###

import sys
from collections import deque
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
dic = {}
li = []
for i in range(m):
    p, y = na()
    li.append([p,y])
    if p not in dic.keys():
        dic[p] = [y]
    else:
        dic[p].append(y)
for v in dic.values():
    v.sort()
for p, y in li:
    for i, n in enumerate(dic[p]):
        if n == y:
            shi = str(p)
            num = str(i + 1)
            pad = 6 - len(shi)
            shi = '0' * pad + shi
            pad = 6 - len(num)
            num = '0' * pad + num
            print(shi + num)

### FIXED CODE ###

import sys
from collections import deque
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
buf = [None] * m
cnt = {k: [] for k in range(n + 1)}
for i in range(m):
    p, y = na()
    cnt[p].append((y, i))
for p, l in cnt.items():
    if not l:
        continue
    l.sort()
    for j, (y, i) in enumerate(l):
        buf[i] = '{:06d}{:06d}'.format(p, j + 1)

print('\n'.join(buf))
### BUGGY CODE ###

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    #a,b,c=map(int, readline().rstrip().split())
    #arr=list(map(int, readline().rstrip().split()))
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    ml=(10**3)*3
    memo=[0]*ml
    for a in arr:
        memo[a]+=1
    for i in range(1,ml):
        memo[i]+=memo[i-1]
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                a=arr[i]
                b=arr[j]
                c=arr[k]
                if (a<b+c) and (b<a+c) and (c<a+b):
                    ans+=1
    print(ans)
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### FIXED CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def bin_search(arr,ls,c):
    l=ls-1
    r = len(arr)
    while (r-l) > 1:
        m = l + (r-l)//2
        if arr[m] >= c:
            r = m
        else:
            l = m
    return l-ls+1

def resolve():
    readline=sys.stdin.readline

    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    arr.sort()
    ans=0
    for i in range(n-2):
        for j in range(i+1,n-1):
            c = arr[i] + arr[j]
            ans += bin_search(arr,j+1,c)
    print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------
### BUGGY CODE ###

import math

class Culuculation():
  H = 0
  K = 0
  H = []
  
  def __init__(self):
    self.N, self.K = (int(x) for x in input().split(' '))
    self.H = [int(x) for x in input().split(' ')]
    
  def culuculation(self):
    #Hを降順にソートしてK回POPし、母数を減らす
    list.sort(self.H, reverse=True)
    for i in range(self.K):
      self.H.pop(0)
      if len(self.H) == 0:
        break
    #残ったリストHを合算して出力
    print(sum(self.H))
    
def main():
  tmp = Culuculation()
  tmp.culuculation()

if __name__=='__main__':
  main()

### FIXED CODE ###

N, K = (int(x) for x in input().split(' '))
H    = [int(x) for x in input().split(' ')]
#ソート処理
list.sort(H, reverse=True)
#K回最大値をHから消す
if N >= K:
  del H[0:K]
else:
  H.clear()
#総和を出力
print(sum(H))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

ans = 0
for i in range(60):
  count_one = sum(a>>i & 1 for a in A)
  ans += count_one * (N - count_one) * (2 ** i)
  
    
print(ans%MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+ 7

ans = 0
two = 1
for i in range(61):
  n = len([ a for a in A if (a >> i) & 1 ])
  ans += (n * (N - n) * two % MOD)
  two *= 2 
print(ans%MOD)
### BUGGY CODE ###

R,C,K=map(int,input().split())
RCV=[list(map(int,input().split())) for i in range(K)]
V=[[0]*(C+1) for i in range(R+1)]
for r,c,v in RCV:
    V[r][c]=v
d=[[[0]*4 for i in range(C+1)] for i in range(R+1)]
for i in range(R):
    for j in range(C):
        m=max(d[i][j+1])
        d[i+1][j+1][0]=m
        d[i+1][j+1][1]=max(d[i+1][j][1],m+V[i+1][j+1],d[i+1][j][0]+V[i+1][j+1])
        d[i+1][j+1][2]=max(d[i+1][j][2],m+V[i+1][j+1],d[i+1][j][1]+V[i+1][j+1])
        d[i+1][j+1][3]=max(d[i+1][j][3],m+V[i+1][j+1],d[i+1][j][2]+V[i+1][j+1])
print(max(d[-1][-1]))

### FIXED CODE ###

import numpy as np
def main(R,C,K,RCV):
    V=np.zeros((R+1,C+1),dtype=np.int64)
    for i in range(K):
        V[RCV[i][0]][RCV[i][1]]=RCV[i][2]
    d=np.zeros((R+1,C+1,4),dtype=np.int64)
    for i in range(R):
        for j in range(C):
            m=max(d[i][j+1])
            d[i+1][j+1][0]=m
            for k in range(3):
                d[i+1][j+1][k+1]=max(d[i+1][j][k+1],m+V[i+1][j+1],d[i+1][j][k]+V[i+1][j+1])
    return max(d[-1][-1])
import sys
readline=sys.stdin.buffer.readline
read=sys.stdin.buffer.read
if sys.argv[-1]=='ONLINE_JUDGE':
    from numba import*
    from numba.pycc import CC
    cc=CC('my_module')
    def cc_export(f,s):
        cc.export(f.__name__,s)(f)
        return njit(f)
    main=cc_export(main,(i8,i8,i8,i8[:,:],))
    cc.compile()
    exit()
R,C,K=np.array(readline().split(),dtype=np.int64)
RCV=np.array(read().split(),dtype=np.int64).reshape(K,3)
from my_module import main
print(main(R,C,K,RCV))
### BUGGY CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(map(int,input().split()))
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

S = list(s())
cnt = 0
N = len(S)
for i in range(N):
    if not S:
        break
    N = len(S)
    if S[0] == 'x':
        if S[N-1] == 'x':
            S = S[1:N-1]
        else:
            cnt += 1
            S.pop(0)
    else:
        a = S[0]
        if S[N-1] == 'x':
            cnt += 1
            S.pop(-1)
        elif S[N-1] == a:
            S = S[1:N-1]
        else:
            print(-1)
            exit()
print(cnt)

### FIXED CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(map(int,input().split()))
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

S = deque(list(s()))
cnt = 0
N = len(S)
for i in range(N):
    N = len(S)
    if N <= 1:
        break
    if S[0] == 'x':
        if S[N-1] == 'x':
            S.pop()
            S.popleft()
        else:
            cnt += 1
            S.popleft()
    else:
        a = S[0]
        if S[N-1] == 'x':
            cnt += 1
            S.pop()
        elif S[N-1] == a:
            S.pop()
            S.popleft()
        else:
            print(-1)
            exit()
print(cnt)
### BUGGY CODE ###

n=int(input())
x = list(map(int, input().split()))

ans=0
total=0

for i in range(n):
  l=i+1
  for l in range(i+1,n):
   
    ans=ans+x[l]
  total=total+x[i]*ans
  ans=0 
   
    
print(total %1000000007)


### FIXED CODE ###

n=int(input())
x = list(map(int, input().split()))

ans=0
total=0
t=sum(x)

for i in range(n):
 
  t=t-x[i]
  total=total+x[i]*(t)
  
   
    
print(total %1000000007)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

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

A = []
B = []

route = [[0 for j in range(N)] for i in range(N)]

for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)
    
    route[_a - 1][_b - 1] = route[_b - 1][_a - 1] = 1

# # 隣接行列
# for i in range(N):
#     for j in range(N):
# 
# for a, b in zip(A, B):
#     route[a - 1][b - 1] = route[b - 1][a - 1] = 1

# # 隣接リスト
# route2 = [[] for n in range(N)]
#
# for a, b in zip(A, B):
#     route2[a - 1].append(b - 1)
#     route2[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while queue:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    for i, node in enumerate(route[now]):
        if node == 0:
            continue

        if i not in visited:

            # for r in route2[now]:
            # for r in range(N):
            #     if r not in visited:
            # if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(i)
            visited.add(i)

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[i]:
                room_depth[i] = min(room_depth[now] + 1, room_depth[i])
            else:
                room_depth[i] = room_depth[now] + 1

            room_sign[i] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)


### FIXED CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

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

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)
### BUGGY CODE ###

N,Q=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(N-1)]
A.sort()
B=[list(map(int,input().split())) for _ in range(Q)]
B.sort()

cost=[0]*(N+1)

for b in B:
	cost[b[0]]+=b[1]

for a in A:
	cost[a[1]] += cost[a[0]]
print(*cost[1:])

### FIXED CODE ###

N,Q=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(N-1)]
A.sort()

cost=[0]*(N+1)

for _ in range(Q):
	a,b=map(int,input().split())
	cost[a]+=b

for a in A:
	cost[a[1]] += cost[a[0]]
print(*cost[1:])
### BUGGY CODE ###

k,s=map(int,input().split())
ans=0
for i in range(k+1):
    for j in range(k+1):
            if s-(i+j) in range(k+1):
                ans+=1
print(ans)

### FIXED CODE ###

k,s=map(int,input().split())
ans=0
for i in range(k+1):
    for j in range(k+1):
            if s-(i+j) in range(k+1):
                ans+=1
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
lenA = len(A)
minA = min(A)

for i in range(M):
  B, C = map(int, input().split())
  if C > minA:
    A.extend([C for _ in range(B)])

A.sort(reverse = True)
l = A[0:lenA]

print(sum(l))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]
lenA = len(A)
minA = min(A)
BC.sort(reverse = True, key = lambda x:x[1])

i = 0
cnt = 0
while cnt < lenA and i < M:
  A.extend([BC[i][1] for _ in range(BC[i][0])])
  cnt += BC[i][0]
  i += 1
A.sort(reverse = True)
l = A[0:lenA]

print(sum(l))
### BUGGY CODE ###

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

for i in range(int(p**(1/n))+2)[::-1]:
  if p%(i**n)==0:
    print(i)
    break

### FIXED CODE ###

n, p = map(int, input().split())
if n==1:
  print(p)
  exit()
elif p==1 or n>=60:
  print(1)
  exit()
for i in range(int(p**(1/n))+1, 0, -1):
  if p%(i**n)==0:
    print(i)
    exit()
### BUGGY CODE ###

A, B, N = map(int,input().split())
mmax=0
N_min = A//B+1
N_max = N if B > N else B
for n in range(N_min, N_max + 1):
    _max = int(A*n/B)-(A*int(n/B))
    if mmax < _max:
        mmax=_max

print(mmax)

### FIXED CODE ###

A, B, N = map(int,input().split())
mmax=0
N_max = N if B > N else B
for n in reversed(range(N_max - A, N_max + 1)):
    _max = int(A*n/B)-(A*int(n/B))
    if mmax < _max:
        mmax=_max

print(mmax)
### BUGGY CODE ###

n = int(input())
s = []
count = 0
for i in range(n):
    s.append(input())
for i in range(n):
    for j in range(i+1, n):
        if sorted(s[i]) == sorted(s[j]):
            count += 1
print(count)

### FIXED CODE ###

n = int(input())
s = []
for i in range(n):
    s.append(''.join(sorted(input())))
s.sort()
count = 1
counts = []
now = s[0]
for i in range(1, n):
    if s[i] == now:
        count += 1
    else:
        if count > 1:
            counts.append(count)
        count = 1
        now = s[i]
if count > 1:
    counts.append(count)
c = 0
for i in counts:
    c += i * (i-1) // 2
print(c)
### BUGGY CODE ###

from heapq import heappop, heappush 
def dijkstra(xs, ys, xg, yg,h,w,k,field):
    # que->(cost, x, y)
    que = [(0, xs, ys)]
    inf = 10 ** 6 * k
    dp = [[inf for _ in range(w+1)] for _ in range(h+1)]
    dp[xs][ys] = 0
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    while que:
        cost, x, y= heappop(que)
        # 現在のコストより高いなら無視する
        if cost > dp[x][y]:
            continue
        if x == xg and y == yg:
            print(cost)
            exit(0)
        for i in range(4):
            for j in range(1, k+1):
                x_, y_ = x+j*dx[i], y+j*dy[i]
                if not field[x_][y_]:
                    break
                if dp[x_][y_] > dp[x][y] + 1:
                    dp[x_][y_] = dp[x][y] + 1
                    heappush(que, (dp[x_][y_], x_, y_))
    print(-1)
        

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2) for _ in range(h+2)]
    inf = 10 ** 6 * k
    for i in range(h):
        # False で覆うことでx,yの制限をなくす。
        s = [True if _ == '.' else False for _ in input()]
        field[i+1] = [False]+s+[False]
    dijkstra(xs, ys, xg, yg, h, w, k, field)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  graph[u].append(v)

# 距離が3のノード間にだけ辺を張り直す
g = [[] for i in range(N)]
for i in range(N):
  d = deque([i])
  for _ in range(3):
    n = len(d)
    for j in range(n):
      node = d.popleft()
      children = graph[node]
      d.extend(children)
  g[i] = d

S, T = map(int, input().split())
S -= 1; T -= 1
d = deque([[S, -1]])
dist = [float('inf')] * N
dist[S] = 0
# 幅優先探索
while d:
  n = len(d)
  for i in range(n):
    node, par = d.popleft()
    children = g[node]
    for child in children:
      if child == par:
        continue
      dist[child] = min(dist[child], dist[node] + 1)
      if child == T:
        print(dist[child])
        quit()
      d.append([child, node])

print(-1)

### FIXED CODE ###

from collections import deque

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

graph = [[] for i in range(3*N)]
for i in range(M):
  u, v = map(int, input().split())
  u, v = 3*(u - 1), 3*(v - 1)
  graph[u].append(v+1)
  graph[u+1].append(v+2)
  graph[u+2].append(v)

s, t = map(int, input().split())
s, t = 3*(s - 1), 3*(t - 1)


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)
### BUGGY CODE ###

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

ans = 1

for i in A:
    ans = ans*i

if ans > int(10**18):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

if A.count(0) != 0:
    print(0)
    sys.exit()

for i in A:

    ans = ans*i
    if ans > int(10**18):
        print(-1)
        sys.exit()
 
if ans > int(10**18):
    print(-1)
else:
    print(ans)