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

N = int(input())
A = list(map(int,input().split()))
MAX = 10**18
ret = 1
for a in A:
  ret *= a
if ret > MAX:
  print(-1)
else:
  print(ret)
         

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
MAX = 10**18
ret = 1
flag = True
if 0 in A:
    print(0)
else:
    for a in A:
        ret *= a
        if ret > MAX:
            print(-1)
            flag = False
            break
    if flag and ret <= MAX:
        print(ret)
### BUGGY CODE ###

paramA, paramB, paramC, paramK = list(map(lambda x: int(x), input().split(' ')))
params = [1 for i in range(paramA)]
params.extend([0 for i in range(paramB)])
params.extend([-1 for i in range(paramC)])

result = 0
for p in params:
    if paramK > 0:
        result += p
        paramK -= 1

print(result)

### FIXED CODE ###

paramA, paramB, paramC, paramK = list(map(lambda x: int(x), input().split(' ')))

result = min(paramA, paramK)
paramK -= paramA
if paramK > 0:
    paramK -= paramB
    if paramK > 0:
        result -= min(paramC, paramK)

print(result)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
res = 1
for i in range(n):
    res *= a[i]
if res > (10**18):
    print(-1)
else:
    print(res)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
res = 1
A.sort()
for i in range(N):
    res *= A[i]
    if res > (10 ** 18):
        print(-1)
        exit()
    elif res == 0:
        print(0)
        exit()
print(res)
### BUGGY CODE ###

s = list(input())
t = list(input())

for i in range(len(s)):
    if s[i] != t[i]:
        be = s[i]
        af = t[i]
        for i in range(len(s)):
            if s[i] == be:
                s[i] = af
            elif s[i] == af:
                s[i] = be

print('Yes') if s == t else print('No')

### FIXED CODE ###

s = list(input())
t = list(input())

mapping = {}
for i in range(len(s)):
    if s[i] in mapping:
        if mapping[s[i]] == t[i]:
            continue
        else:
            print('No')
            break
    elif t[i] in mapping.values():
        print('No')
        break
    else:
        mapping[s[i]] = t[i]
else:
    print('Yes')
### BUGGY CODE ###

n=int(input())
s=input()
r=g=b=0
for i in range(n):
    if s[i]=="R":
        r+=1
    elif s[i]=="G":
        g+=1
    else:
        b+=1
ans=r*g*b
sub=0
for i in range(n-2):
    for j in range(i+1,n-1):
        k=j+(j-i)
        if s[i]==s[j]:
            continue
        if k>=n or s[i]==s[k] or s[j]==s[k]:
            continue
        sub+=1
print(ans-sub)

### FIXED CODE ###

n=int(input())
s=input()
r=g=b=0
for i in range(n):
    if s[i]=="R":
        r+=1
    elif s[i]=="G":
        g+=1
    else:
        b+=1
ans=r*g*b
sub=0
for i in range(n-2):
    for j in range(i+1,n-1):
        k=j+(j-i)
        if s[i]==s[j]:
            continue
        if k>=n or s[i]==s[k] or s[j]==s[k]:
            continue
        sub+=1
print(ans-sub)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
minans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n,u,v=map(int,input().split())
u-=1;v-=1
G=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    G[b].append(a)
D=[-1]*n
maxD=[-1]*n

def make_tree_dfs(n,d):
    D[n]=d
    tmp=0
    f=True
    for gi in G[n]:
        if D[gi]==-1:
            f=False
            tmp=max(tmp,make_tree_dfs(gi,d+1))
    if f: tmp=d
    maxD[n]=tmp
    return tmp

make_tree_dfs(v,0)
sdis=D[u]

def good_dfs(v,d,sdis):
    f=True
    for gi in G[v]:
        if D[gi]==d-1 and d-1>sdis-(d-1):
            return good_dfs(gi,d-1,sdis)
    return (maxD[v],d)

gd,orid=good_dfs(u,D[u],sdis)
k=orid-(sdis-orid)
print(gd-orid+(sdis-orid)+k-1)
# print(D)
# print(maxD)
# print(sdis,orid,gd,k)
        







### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
minans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n,u,v=map(int,input().split())
u-=1;v-=1
G=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    G[b].append(a)
D=[-1]*n
maxD=[-1]*n

def make_tree_dfs(n,d):
    D[n]=d
    tmp=0
    f=True
    for gi in G[n]:
        if D[gi]==-1:
            f=False
            tmp=max(tmp,make_tree_dfs(gi,d+1))
    if f: tmp=d
    maxD[n]=tmp
    return tmp

make_tree_dfs(v,0)
sdis=D[u]

def good_dfs(v,d,sdis):
    f=True
    for gi in G[v]:
        if D[gi]==d-1 and d-1>sdis-(d-1):
            return good_dfs(gi,d-1,sdis)
    return (maxD[v],d)

gd,orid=good_dfs(u,D[u],sdis)
k=orid-(sdis-orid)
print(gd-orid+(sdis-orid)+k-1)
# print(D)
# print(maxD)
# print(sdis,orid,gd,k)
### BUGGY CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    def dfs(u, ou=-1, d=0):
        if d < depth[u]: return
        parent[u] = ou + 1
        depth[u] = d
        for ku in to[u]:
            dfs(ku, u, d + 1)

    to = defaultdict(list)
    n, m = map(int, input().split())
    CntInDegree = [0] * n
    parent = [-1] * n
    depth = [-1] * n
    for _ in range(n + m - 1):
        a, b = map(int1, input().split())
        to[a].append(b)
        CntInDegree[b] += 1
    root = CntInDegree.index(0)
    # print(root)
    dfs(root)
    print(*parent, sep="\n")

main()


### FIXED CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    to = defaultdict(set)
    ot = defaultdict(set)
    n, m = map(int, input().split())
    cnt_in_degree = [0] * n
    parent = [-1] * n
    for _ in range(n + m - 1):
        a, b = map(int1, input().split())
        cnt_in_degree[b] += 1
        to[a].add(b)
        ot[b].add(a)
    root = cnt_in_degree.index(0)
    parent[root] = -1
    part_roots = [root]
    cnt_decide = 1
    while cnt_decide < n:
        u = part_roots.pop()
        for ku in to[u]:
            if len(ot[ku]) == 1:
                parent[ku] = u
                part_roots.append(ku)
                cnt_decide += 1
            else:
                ot[ku].remove(u)
    for u in parent:
        print(u + 1)

main()
### BUGGY CODE ###

# 再帰関数使用時は再帰上限を十分にとること
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

# グローバル変数定義
INF = 10 ** 13
N, W = map(int, input().split())

# knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
# knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
knapsack = [list(map(int, input().split())) for _ in range(N)]

# db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
db = [[INF] * W for _ in range(N)]


def dfs(n, w):
    """
    品物に対する深さ優先探索による全探索（メモ化再帰）。

    Args:
        n (int) : 見てきた品物の数
        w (int) : ここまでの重さの総和

    Returns:
        v (int) : 価値の総和の最大値
    """

    # 終了条件：現在の個数が全ての品物の個数を越える
    if n >= N:
        return 0

    if w + knapsack[n][0] > W:
        # １つ前までの重さ + 今回の品物の重さが重さの最大値を越えていたら今回の品物は選べない
        return dfs(n + 1, w)
    else:
        # 今回の品物を選ぶか選ばないかで全探索
        return max([dfs(n + 1, w), dfs(n + 1, w + knapsack[n][0]) + knapsack[n][1]])


def main():
    out = dfs(0, 0)
    print(out)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
readline = sys.stdin.readline


def chmax(a, b):
    """
    2値の大きい値を返す

    Args:
        a   (int)   : 値１
        b   (int)   : 値２
    Return:
        a   (int)   : aまたはbの大きい値
    """
    if a < b:
        a = b
    return a


def main():

    N, W = map(int, readline().split())

    # knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
    # knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
    knapsack = [list(map(int, readline().split())) for _ in range(N)]

    # db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for n in range(1, N + 1):
        for w in range(W + 1):
            if w - knapsack[n - 1][0] < 0:
                dp[n][w] = dp[n - 1][w]
            else:
                dp[n][w] = chmax(dp[n - 1][w], dp[n - 1]
                                 [w - knapsack[n - 1][0]] + knapsack[n - 1][1])

    print(dp[N][W])


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

a, b, c = input().split()        
a, b, c = int(a), int(b), int(c) 
fl = False                       
ab = a+b                         
ac = a+c                         
bc = b+c                         
while(1):                        
    if ab == c:                  
        fl = True                
        break                    
    if bc == a:                  
        fl = True                
        break                    
    if ac == b:                  
        fl = True                
        break                    
if fl:                           
    print('Yes')                 
else:                            
    print('No')                  
                                 


### FIXED CODE ###

a, b, c = input().split()        
a, b, c = int(a), int(b), int(c) 
fl = False                       
ab = a+b                         
ac = a+c                         
bc = b+c                         
while(1):                        
    if ab == c:                  
        fl = True                
        break                    
    if bc == a:                  
        fl = True                
        break                    
    if ac == b:                  
        fl = True                
        break                    
    break                        
if fl:                           
    print('Yes')                 
else:                            
    print('No')
### BUGGY CODE ###

from collections import Counter
s=list(input())
lst=[]  #sのリバース
lst2=[] #累積和を2019で割ったあまり

num=0
for j in reversed(range(0,len(s))):
    
    lst2.append(num%2019)
    num+=int(s[j])*10**(len(s)-j-1)
lst2.append(num%2019)

ans=0
cou=dict(Counter(lst2))
for x in cou.values():
    ans+=x*(x-1)/2
print(int(ans))


### FIXED CODE ###

from collections import Counter

s=input()[::-1]
ans=0
lst=[0]
num=0
p=1
for i in s:
    lst.append((int(i)*p+lst[-1])%2019)
    p=p*10%2019

ans=sum(x*(x-1)//2 for x in Counter(lst).values())
print(ans)
### BUGGY CODE ###

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

ans = 0
for i, p in enumerate(p_list):
    if p == min(p_list[:i+1]): ans += 1
print(ans)

### FIXED CODE ###

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

ans = 0
m = 10**10

for p in p_list:
    if p <= m:
        ans += 1
        m = p
print(ans)
### BUGGY CODE ###

import sys
from collections import defaultdict, deque
sys.setrecursionlimit(10**9)
N = int(input())
es = defaultdict(list)
se = defaultdict(list)
ins = [0]*(N*(N-1)//2)
dp = [-1]*(N*(N-1)//2)
ID = [[0]*N for i in range(N)]
count = 0
for i in range(N):
  for j in range(N):
    if i<j:
      ID[i][j] = count
      count += 1
def TP_sort(E, ins, start):
  q = deque(start)
  res = -1
  while q:
    p = q.popleft()
    res = p
    for c in E[p]:
      ins[c] -= 1
      if ins[c]==0:
        q.append(c)
  for i in ins:
    if i>0:
      return -1
  return res

def dfs(e):
  if dp[e]!=-1:
    return dp[e]
  m = 0
  for ex in se[e]:
    x = dfs(ex)
    if x>m:
      m = x
  dp[e] = m+1
  return m+1

for i in range(N):
  inf = [int(i)-1 for i in input().split()]
  for j in range(N-2):
    x = min(i, inf[j])
    y = max(i, inf[j])
    nx = min(i, inf[j+1])
    ny = max(i, inf[j+1])
    t = ID[x][y]
    nt = ID[nx][ny]
    es[t] += [nt]
    se[nt] += [t]
    ins[nt] += 1
start = [v1 for v1 in range(len(ins)) if ins[v1]==0]
end = TP_sort(es, ins, start)
if end==-1:
  print(-1)
else:
  for i in start:
    dp[i] = 0
  print(dfs(end)+1)

### FIXED CODE ###

N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if es[j]==[]:
    return
  if es[j][-1]==i:
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 0
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    x = es[i].pop()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

import heapq

tmp = list(map(int, input().split()))
x = tmp[0]
y = tmp[1]
z = tmp[2]
k = tmp[3]
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

log = [[[False for _ in range(z)] for _ in range(y)] for _ in range(x)]

cnt = 0
h = []
heapq.heappush(h, (-(a[0]+b[0]+c[0]), 0, 0, 0))
for i in range(k): 
  tmp = heapq.heappop(h)
  print(-tmp[0])
  if tmp[1]+1 < x and log[tmp[1]+1][tmp[2]][tmp[3]] == False:
    heapq.heappush(h, (-(a[tmp[1]+1]+b[tmp[2]]+c[tmp[3]]), tmp[1]+1, tmp[2], tmp[3]))
    log[tmp[1]+1][tmp[2]][tmp[3]] = True
  if tmp[2]+1 < y and log[tmp[1]][tmp[2]+1][tmp[3]] == False:
    heapq.heappush(h, (-(a[tmp[1]]+b[tmp[2]+1]+c[tmp[3]]), tmp[1], tmp[2]+1, tmp[3]))
    log[tmp[1]][tmp[2]+1][tmp[3]] = True
  if tmp[3]+1 < z and log[tmp[1]][tmp[2]][tmp[3]+1] == False:
    heapq.heappush(h, (-(a[tmp[1]]+b[tmp[2]]+c[tmp[3]+1]), tmp[1], tmp[2], tmp[3]+1))
    log[tmp[1]][tmp[2]][tmp[3]+1] = True

### FIXED CODE ###

tmp = list(map(int, input().split()))
x = tmp[0]
y = tmp[1]
z = tmp[2]
k = tmp[3]
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

ansl = []
for p in range(x):
  if p > k:
    break
  for q in range(y):
    if p * q > k:
      break
    for r in range(z):
      if p * q * r > k:
        break
      ansl.append(a[p] + b[q] + c[r])

ansl.sort(reverse=True)

for i in range(k):
  print(ansl[i])
### BUGGY CODE ###

import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7


n,m = MAP()
a = MAP()
heapify(a)
for i in range(m):
    b,c = MAP()
    for j in range(b):
        tmp = heappop(a)
        if tmp<c:
            heappush(a,c)
        else:
            heappush(a,tmp)
print(sum(a))

### FIXED CODE ###

import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7


n, m = MAP()
a = MAP()
p = [(a[i], 1) for i in range(n)]
for j in range(m):
    b, c = MAP()
    p.append((c, b))
p.sort(reverse=True)
ans, cnt = 0, n
for (v, c) in p:
    use = min(c, cnt)
    ans += use * v
    cnt -= use
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, w = map(int, input().split())
    goods = [list(map(int, input().split())) for _ in range(n)]

    dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    for j in range(1, w + 1):
        for i in range(1, n + 1):
            w, v = goods[i - 1]
            if j - w >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]

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


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, w = map(int, input().split())
    goods = [list(map(int, input().split())) for _ in range(n)]

    dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    for j in range(1, w + 1):
        for i in range(1, n + 1):
            w, v = goods[i - 1]
            if j - w >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]

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


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

from collections import deque
N,M,K = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]
friends = [set() for _ in range(N)]
blocks = [set() for _ in range(N)]
links = [set() for _ in range(N)]
searched = [0] * N
ans = [0] * N
d = deque()
for x, y in AB:
    friends[x-1].add(y-1)
    friends[y-1].add(x-1)
for x, y in CD:
    blocks[x-1].add(y-1)
    blocks[y-1].add(x-1)
for i in range(N):
    if searched[i]:
        continue
    trace = set()
    d.append(i)
    while d:
        temp = d.popleft()
        trace.add(temp)
        searched[temp] = 1
        for x in friends[temp]:
            if searched[x] == 0:
                d.append(x)
    for person in trace:
        links[person] = trace
for i in range(N):
    ans[i] = len(links[i]) - 1 - len(links[i]&friends[i]) - len(links[i]&blocks[i])
print(*ans)

### FIXED CODE ###

from collections import deque
N,M,K = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]
friends = [set() for _ in range(N)]
blocks = [set() for _ in range(N)]
searched = [0] * N
ans = [0] * N
d = deque()
for x, y in AB:
    friends[x-1].add(y-1)
    friends[y-1].add(x-1)
for x, y in CD:
    blocks[x-1].add(y-1)
    blocks[y-1].add(x-1)
for i in range(N):
    if searched[i]:
        continue
    trace = set()
    d.append(i)
    trace.add(i)
    searched[i] = 1
    while d:
        temp = d.popleft()
        for x in friends[temp]:
            if searched[x] == 0:
                d.append(x)
                trace.add(x)
                searched[x] = 1
    chain = len(trace)
    for j in trace:
        ans[j] = chain - 1 - len(trace&friends[j]) - len(trace&blocks[j])
print(*ans)
### BUGGY CODE ###

import itertools

n, k = map(int, input().split())
p_list = [[0] * 2 for i in range(n)]

for i in range(n):
    x, y = map(int, input().split())
    p_list[i] = [x, y]

k_list = list(itertools.combinations(range(n), k))
min_area = ((10 ** 9) * 2) ** 2

for ki in k_list:
    x_list = []
    y_list = []
    for i in ki:
        x_list.append(p_list[i][0])
        y_list.append(p_list[i][1])
    x_max = max(x_list)
    x_min = min(x_list)
    y_max = max(y_list)
    y_min = min(y_list)
    area = abs(x_max - x_min) * abs(y_max - y_min)
    if area < min_area:
        min_area = area

print(min_area)



### FIXED CODE ###

N, K = map(int, input().split())
p_list = [[0] * 2 for i in range(N)]
for i in range(N):
    x, y = map(int, input().split())
    p_list[i] = [x, y]

p_list.sort()
ans = float('inf')
for i in range(N - K + 1):
    for j in range(i + K - 1, N):
        x = abs(p_list[j][0] - p_list[i][0])
        y_list = []
        for k in range(i, j + 1):
            y_list.append((p_list[k][1]))
        y_list.sort()
        for k in range(len(y_list) - K + 1):
            ans = min(ans, x * abs(y_list[k + K - 1] - y_list[k]))

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

n=int(input())
a=[0 for _ in range(n)]
for i in range(n):
    a[i]=int(input())
M=max(a)
ans=0
for i in range(n):
    if(a[i]!=M):
        ans=M
    else:
        ans=0
        for j in range(n-1):
            if(j>=i):
                j+=1
            ans=max(ans,a[j])
        
    print(ans)        



### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline

def main():
    n=int(input())
    a=[0 for _ in range(n)]
    for i in range(n):
        a[i]=int(input())
    M=max(a)
    cnt=0
    ans=0
    S=0
    for i in range(n):
        if(a[i]!=M and a[i]>S):
            S=a[i]
        elif(a[i]==M):
            cnt+=1
    
    for i in range(n):
        if(a[i]!=M or cnt>1):
            ans=M
        else:
            ans=S
        print(ans)        
main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
import copy

N,M,P=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
q=deque()
q.append(N)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in rev_al[fro]:
		if Visit[to]==0:
			q.append(to)
			
Visit1=Visit

#スタートからBFS
q=deque()
q.append(1)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in al[fro]:
		if Visit[to]==0:
			q.append(to)

Visit2=Visit

#1からもNからも到達可能な頂点の集合
V=[]
for v1,v2 in zip(Visit1,Visit2):
	V.append(v1&v2)

new_N=sum(V)

D=[ float("-inf") for _ in range(N+1) ]	#頂点１からの距離 1-indexed
D[1]=0

fedge=[]	#必要な要素だけをフィルターした辺集合
for a,b,c in edge:
	if V[a]==1 and V[b]==1:
		fedge.append((a,b,c))

#ベルマンフォード
for cnt in range(new_N):
	for a,b,c in fedge:
		if cnt==new_N-1 and D[b]!=max( D[b],D[a]+c ):
			print -1
			quit()
		D[b]=max( D[b],D[a]+c )

print max(0,D[N])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M,P=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(N)
Visit[N]=1
while q:
	fro=q.popleft()
	for to in rev_al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)
			
Visit1=Visit

#スタートからBFS
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(1)
Visit[1]=1
while q:
	fro=q.popleft()
	for to in al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)

Visit2=Visit

#1からもNからも到達可能な頂点の集合
V=[]
for v1,v2 in zip(Visit1,Visit2):
	V.append(v1&v2)

new_N=sum(V)

fedge=[]	#必要な要素だけをフィルターした辺集合
for a,b,c in edge:
	if V[a]==1 and V[b]==1:
		fedge.append((a,b,c))


D=[ float("-inf") ]*(N+1)	#頂点１からの距離 1-indexed
D[1]=0

#ベルマンフォード
for i in range(new_N):
	for a,b,c in fedge:
		if D[a]==float("-inf"): continue
		alt=D[a]+c
		if D[b]<alt:
			D[b]=alt
			if i==new_N-1:
				print -1
				quit()

print max(0,D[N])
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
  l,r=map(int,input().split())
  ans=0
  for j in range(l-1,r-1):
    if s[j]=='A' and s[j+1]=='C':
      ans+=1
  print(ans)

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
B=[0]*N
for i in range(1,N):
    if S[i-1]=='A' and S[i]=='C':
        B[i]=B[i-1]+1
    else:
        B[i]=B[i-1]
for i in range(Q):
    l,r=map(int,input().split())
    print(B[r-1]-B[l-1])
### BUGGY CODE ###

import queue

# input
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]

# bfs
bfs = [[-1 for j in range(W)] for i in range(H)]
que = queue.Queue()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '#'):
            que.put((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while(que.qsize()):
    p = que.get_nowait()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.put((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1

# print ans
print(max([max(l) for l in bfs]))


### FIXED CODE ###

from collections import deque

# input
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]

# bfs
bfs = [[-1 for j in range(W)] for i in range(H)]
que = deque()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '#'):
            que.append((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while(len(que)):
    p = que.popleft()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.append((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1

# print ans
print(max([max(l) for l in bfs]))