Harryxun/stf_run huggingface dataset:
# AOJ ITP1_8_C
import sys

def numinput():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a

def main():
    counts = []
    for i in range(26): counts.append(0)

    while True:
        string = input()
        if !string[0]: break
        for k in range(len(string)):
            c = string[k]
            if 97 <= ord(c) <= 122:
                counts[ord(c) - 97] += 1
            elif 65 <= ord(c) <= 90:
                counts[ord(c) - 65] += 1

    # 結果を出力。
    for i in range(26):
        print(chr(97 + i) + " : " + str(counts[i]))

if __name__ == "__main__":
    main()



### FIXED CODE ###

# AOJ ITP1_8_C

import sys

def main():
    counts = []
    for i in range(26): counts.append(0)

    lines = sys.stdin.readlines()

    for i in range(len(lines)):
        string = lines[i]
        for k in range(len(string)):
            c = string[k]
            if 97 <= ord(c) <= 122:
                counts[ord(c) - 97] += 1
            elif 65 <= ord(c) <= 90:
                counts[ord(c) - 65] += 1

    # 結果を出力。
    for i in range(26):
        print(chr(97 + i) + " : " + str(counts[i]))

if __name__ == "__main__":
    main()

# Accepted.
import math

a, b = map(int, input().split())
print((a*b) // math.gcd(a, b))

### FIXED CODE ###

from fractions import gcd

a, b = map(int, input().split())
print((a*b) // gcd(a, b))
N,A,B=map(int,input().split())
#print(N,A,B)

moji="b"*A+"r"*B
#print(moji)

if N==A+B:
    print(A)
elif N>A+B:
    if N%(A+B)>A:
        print((N//(A+B))*A+A)
    else:
        print((N//(A+B))*A+N%(A+B))
else:
    print(A)

### FIXED CODE ###

N,A,B=map(int,input().split())
#print(N,A,B)

#moji="b"*A+"r"*B
#print(moji)

if A==B==0:
    print(0)
elif A==0:
    print(0)
else:

    if N==(A+B):
        print(A)
    elif N>A+B:
        if N%(A+B)>A:
            print((N//(A+B))*A+A)
        else:
            print((N//(A+B))*A+N%(A+B))
    else:
        if N<A:
            print(N)
        else:
            print(A)
A=input
if A='hi' or A='hihi' or A='hihihi' or A='hihihihi' or A='hihihihihi' or A='hih' or A='hihih' or A='hihihih' or A='hihihihih':
    print('Yes')
else:
    print('No')

### FIXED CODE ###

A=input()
if A=='hi' or A=='hihi' or A=='hihihi' or A=='hihihihi' or A=='hihihihihi':
    print('Yes')
else:
    print('No')
#--import&define---------------------
import math

def yes():
    print("Yes")
def no():
    print("No")
#--my_library--------------------------------
#mapを利用した入力
# x,y = map(int,input().split())

#forを利用した入力
#l = []
#for i in range():
#    l.append(int(input()))

#intの最大値
#x = 2147483647
#--以下解答---------------------------------
l = []
ansL = []
x = 2147483647
index = 0
for i in range(5):
   l.append( int(input()) )
   ansL.append( int(l[i]%10) )
   if ansL[i]>0 and ansL[i]<x:
      index = i

print(l)
ans = 0
for i in range(5):
    if i == dex:
        ans += l[i]
    elif l[i]%10 != 0:
        ans += int(l[i]/10)*10 +10
    else:
        ans += l[i]
    print(ans)

print(ans)




### FIXED CODE ###

l = []
x = 2147483647
index = 0
for i in range(5):
   l.append( int(input()) )
   n = int(l[i]%10)
   if n>0 and n<x:
      x = n
      index = i

ans = 0
for i in range(5):
    if i == index:
        ans += l[i]
    elif l[i]%10 != 0:
        ans += int(l[i]/10)*10 +10
    else:
        ans += l[i]

print(ans)
N = int(input())
xyz = []
for _ in range(N):
    temp = list(map(int, input().split()))
    xyz.append(temp)

for i in range(101):
    for j in range(101):
        h = xyz[0][2] + abs(xyz[0][0] - i) + abs(xyz[0][1] - j)

        count = N-1
        for n in range(1,N):
            g = h - abs(i - xyz[n][0]) - abs(j - xyz[n][1])
            if g == xyz[n][2]:
                count -= 1
        
        if count == 0:
            ans = [str(i), str(j), str(h)]
            break

ans_s = ' '.join(ans)
print(ans_s)

### FIXED CODE ###

N = int(input())
xyz = []

for _ in range(N):
    temp = list(map(int, input().split()))
    xyz.append(temp)


if N == 1:
    ans = [str(xyz[0][0]), str(xyz[0][1]), str(xyz[0][2])]
else:
    for i in range(101):
        for j in range(101):
            for k in range(N):
                if xyz[k][2] >= 1:      
                    h = max(xyz[k][2] + abs(xyz[k][0] - i) + abs(xyz[k][1] - j),0)

                    count = N
                    for n in range(0,N):
                        g = max(h - abs(i - xyz[n][0]) - abs(j - xyz[n][1]),0)
                        if g == xyz[n][2]:
                            count -= 1
                    
                    if count == 0:
                        ans = [str(i), str(j), str(h)]
                        break
                    break

ans_s = ' '.join(ans)
print(ans_s)
X,K,D = map(int,input().split())
X = abs(X)
X_div_D = X//D

p_min = X % D
n_min = abs(p_min - D)

if p_min <= n_min:
  ans_min = p_min
  min_idx = X_div_D
else:
  ans = min = n_min
  min_idx = X_div_D + 1
  
if K <= min_idx:
  print(X - K * D)
else:
  if (K - min_idx) % 2 == 0:
    print(ans_min)
  else:
    print(abs(ans_min - D))

### FIXED CODE ###

X,K,D = map(int,input().split())
X = abs(X)
X_div_D = X//D

ans_min = X % D

if K <= X_div_D:
  print(X - K * D)
else:
  if (K % 2) ^ (X_div_D % 2) == 0:
    print(ans_min)
  else:
    print(abs(ans_min - D))
A = int(input())
B = int(input())

if A <= 8 and B <= 8:
    print('Yay!')
else:
    print(':(')

### FIXED CODE ###

A, B = map(int, input().split())

if A <= 8 and B <= 8:
    print('Yay!')
else:
    print(':(')
a = input()
print(int(a))


### FIXED CODE ###

a, b, c = input().split()
a = int(a)
c = int(c)
if b == '+':
  print(a + c)
else:
  print(a - c)
N = int(input())
A = list(map(int,input().split()))
dp = [-1]*N
dp[0] = 0
dp[1] = abs(A[1] - A[0])


def rec(i):
  if dp[i] != -1:
    return dp[i]
  dp[i] = min(rec(i-1) + abs(A[i-1] - A[i]), rec(i-2) + abs(A[i-2] - A[i]))
  return dp[i]

print(rec(N-1))

### FIXED CODE ###

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

def solve():
  dp = [0]*N
  dp[1] = abs(A[1] - A[0])
  for i in range(2,N):
    dp[i] = min((dp[i-1] + abs(A[i] - A[i-1])), (dp[i-2] + abs(A[i] - A[i-2])))
  return dp

dp = solve()
print(dp[N-1])
def opeCounter(S, K):
    T = S * K
    c = 0
    i = 1
    while i < len(T):
        if T[i-1] == T[i]:
            c += 1
            i += 1
        i += 1
    return c

def agc039a(S, K):
    s1 = opeCounter(S, 1)
    s2 = opeCounter(S, 2)
    s3 = opeCounter(S, 3)
    d1 = s2 - s1
    d2 = s3 - s2

    ans = 0
    if d1 == d2: ans = s1 + d1 * (K-1)
    else:
        if(k%2 != 0): ans = s1 + (d1+d2) * ((k+2-1)/2-1) ##(k/2):roundup
        else: ans = s2 + (d1+d2) * (k/2-1)
    return ans

S = input()
K = int(input())
print(agc039a(S, K))

### FIXED CODE ###

def opeCounter(S, K):
    T = S * K
    c = 0
    i = 1
    while i < len(T):
        if T[i-1] == T[i]:
            c += 1
            i += 1
        i += 1
    return c

def agc039a(S, K):
    s1 = opeCounter(S, 1)
    s2 = opeCounter(S, 2)
    s3 = opeCounter(S, 3)
    d1 = s2 - s1
    d2 = s3 - s2

    ans = 0
    if d1 == d2: ans = s1 + d1 * (K-1)
    else:
        if(K%2 != 0): ans = s1 + (d1+d2) * ((K+2-1)//2-1) ##(k/2):roundup
        else: ans = s2 + (d1+d2) * (K//2-1)
    return ans

S = input()
K = int(input())
print(agc039a(S, K))
import math

a,b,h,m=map(int,input().split())

aa=a*a
bb=b*b


mm=m*6
if m != 0:
    hh=h*30+30*m/60
else:
    hh=h*30

cos = math.cos(math.radians(abs(hh-mm)))
#print(cos)
cc=aa+bb-2*a*b*cos

c=math.sqrt(cc)

print(c)



### FIXED CODE ###

a=input()

if a[-1]=='3':
    print('bon')
elif a[-1]=='0' or a[-1]=='1' or a[-1]=='6' or a[-1]=='8':
    print('pon')
elif a[-1]=='2' or a[-1]=='4' or a[-1]=='5' or a[-1]=='7' or a[-1]=='9':
    print('hon')
S = map(int, input().split())
d = S[0] - S[1]
if d <= 0:
  print(0)
else:
  print(d)
  

### FIXED CODE ###

l = list(map(int, input().split()))
if l[0] - l[1] <= 0:
  print('0')
else:
  print(l[0] - l[1])
a, b = map(int,input().split())
x = a + b
y = a - b
z = a * b
O = sorted(list(x, y, z),reverse=True)
print(O[0])


### FIXED CODE ###


a, b = map(int, input().split())
x = a + b
y = a - b
z = a * b
O = [x,y,z]
O = sorted(O,reverse=1)
print(O[0])
a = int(input())
b = int(input())

if a * b % 2 == 0:
    print("Even")
else:
    print("Odd")

### FIXED CODE ###

a, b = map(int, input().split())

if a * b % 2 == 0:
    print("Even")
else:
    print("Odd")
import itertools
from tqdm import tqdm
n, k = map(int, input().split())

def c(n):
    if n <= 2:
        return 1
    return n * (n - 1) // 2


if k <= (n - 1) * (n - 2) // 2:
#         return -1
# if n > 2 and k <= c(n - 1):
    print(n - 1 + c(n - 1) - k)
    nodes = list(range(2, n + 1))
    for i in nodes:
        print(1, i)

    combi = itertools.combinations(nodes, 2)
    for i in range(c(n - 1) - k):
        print(*next(combi))
else:
    print(-1)


### FIXED CODE ###

import itertools
n, k = map(int, input().split())

def c(n):
    if n <= 2:
        return 1
    return n * (n - 1) // 2


if n > 2 and k <= c(n - 1):
    print(n - 1 + c(n - 1) - k)
    nodes = list(range(2, n + 1))
    for i in nodes:
        print(1, i)

    combi = itertools.combinations(nodes, 2)
    for i in range(c(n - 1) - k):
        print(*next(combi))
else:
    print("1\n1 2" if k == 0 else -1)
a, b = map(int, input().split())
sum = 0
for i in range(1,2):
	if a < b:
      sum += b
      b -= 1
    else:
      sum += a
      a -= 1
print('sum')

### FIXED CODE ###

A,B = map(int, input().split())
sum = 0
for i in range(2):
  if A < B:
    sum += B
    B -= 1
  else:
    sum += A
    A -= 1
print(sum)
s = input()
t = input()
dp - [[0 for _ in rannge(len(s)+1)] for i in range(len(t)+1)]
for i in range(len(s)+1):
    dp[i][0] = 0
for j in range(len(t)+1):
    dp[0][j] = 0
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1] == t[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
print(dp[len(s)][len(t)])

### FIXED CODE ###

import numpy as np
 
t = np.array(list(input()), dtype='U1')
s = np.array(list(input()), dtype='U1')
 
ls = len(s)
lt = len(t)
 
eq = s[:, None] == t[None, :]
dp = [np.zeros(lt+1, dtype=np.int16)]
 
# solve
for i in range(ls):
    prev = dp[-1].copy()
    np.maximum(prev[1:], prev[:-1] + eq[i], out = prev[1:])
    np.maximum.accumulate(prev, out = prev)
    dp.append(prev)
 
# print([list(line) for line in dp])
 
# restore
l = dp[-1][-1]
res = ''
i, j = ls, lt
while i > 0 and j > 0:
    if eq[i-1][j-1]:
        res += s[i-1]
        i, j = i-1, j-1
        continue
    
    if dp[i-1][j] > dp[i][j-1]:
        i -= 1
    else:
        j -= 1
 
print(res[::-1])
def gcd(a,b):
    m = max(a,b)
    n = min(a,b)
    if n==0:
        return m
    return gcd(n, m%n)

def lcm(a,b):
    return (a*b)/gcd(a,b)

N = input()
Ti = []

for i in range(int(N)):
    tmp = input()
    Ti.append(int(tmp))
Ti.sort()

ans_lcm = lcm(Ti[0],Ti[1])
for i in range(2,len(Ti)):
    ans_lcm = lcm(ans_lcm,Ti[i])
print(int(ans_lcm))

### FIXED CODE ###

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

def lcm(a,b):
    return (a*b)//gcd(a,b)

N = input()
Ti = []

for i in range(int(N)):
    tmp = input()
    Ti.append(int(tmp))

ans_lcm = 1
for i in range(len(Ti)):
    ans_lcm = lcm(ans_lcm,Ti[i])
print(ans_lcm)
import sys
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
b = [-1] * n
now = 0
count = 0
history = []

while b[now] == -1:
  history.append(now+1)
  b[now] = count
  count += 1
  if count == k:
    print(a[now])
    sys.exit()
  if a[now] == now+1:
    print(a[now])
    sys.exit()
  now = a[now]-1

if now != 0:
  k -= now+1
  for i in range(now+1):
    history.pop(0)     

print(history[k % len(history)])

### FIXED CODE ###

n, k = map(int, input().split())
a = [int(i) for i in input().split()]
b = [-1] * (n+1)
now = 1
history = []

while b[now] == -1:
  b[now] = len(history)
  history.append(now)
  now = a[now-1]

c = len(history) - b[now]
l = b[now]

if k < l:
  print(history[k])
else:
  k -= l
  k %= c
  print(history[l+k])
N=int(input())
A=[int(x) for x in input().split()]
B=[0]*9
for i in range(N):
  R=A[i]//400
  if R>8:
    R=8
  B[R] +=1
answer_min=0
for i in range(8):
  if not B[i]==0:
    answer_min +=1
answer_max=answer_min+B[8]
if answer_max>8:
  answer_max=8
if answer_min=0:
  answer_min=1
print(answer_min,answer_max)

### FIXED CODE ###

N=int(input())
A=[int(x) for x in input().split()]
B=[0]*9
for i in range(N):
  R=A[i]//400
  if R>8:
    R=8
  B[R] +=1
answer_min=0
for i in range(8):
  if not B[i]==0:
    answer_min +=1
answer_max=answer_min+B[8]
if answer_min==0:
  answer_min=1
print(answer_min,answer_max)
from sys import stdin

N,*datas = [int(i) for i in stdin.readlines()]
now_max = max(datas[1:])
max_index = (N-1) - reversed(datas).index(now_max)
_min = min(datas)
min_index = datas.index(_min)

if max_index > min_index:
    diff = now_max - _min
else:
    diff = now_max - datas[0]
    
    for i in range(1,N-1):
        if i == max_index:
            now_max = max(datas[i+1:])
            max_index = datas.index(now_max,i+1)
        new_diff = now_max - datas[i]
        if diff < new_diff:
            diff = new_diff

print(diff)


### FIXED CODE ###

from sys import stdin

N,*datas = [int(i) for i in stdin.readlines()]
now_max = max(datas[1:])
max_index = datas.index(now_max)
diff = now_max - datas[0]

for i in range(1,N-1):
    if i == max_index:
        now_max = max(datas[i+1:])
        max_index = datas.index(now_max,i+1)
    new_diff = now_max - datas[i]
    if diff < new_diff:
        diff = new_diff

print(diff)
N = int(input())
a = [int(input()) for i in range(n)]

#最初はボタン１が光っている
index = 1
#押した回数0からスタート
count = 0

while count < N:
  
  if a[index-1]==2:
    count += 1
    print(count)
    exit()
    
  else:
    count += 1
    #次に光るボタン
    index=a[index-1]

print(-1)


### FIXED CODE ###

N = int(input())
a = [int(input()) for i in range(N)]

#最初はボタン１が光っている
index = 1

#押した回数0からスタート
count = 0

while count < N:
  
  if a[index-1]==2:
    count += 1
    #print(str(2) + "!!")
    print(count)
    exit()
    
  else:
    #ボタン押す
    count += 1
    #次に光るボタンの番号
    index=a[index-1]
    #print(str(index) + "!!")

print(-1)
#l = list(map(int, input().split(' ')))

#num = int(input())
#S = str(input())
# k = (X - Ai - Bj) / C
# C = 0
#
A=int(input())
B=int(input())
C=int(input())
X=int(input())
sum = 0

for i in range(0,A+1):
    for j in range(0,B+1):
        for k in range(0,C+1):
            if(500*i+100*j+50*k==X):
                sum+=

print(sum)


### FIXED CODE ###

#l = list(map(int, input().split(' ')))

#num = int(input())
#S = str(input())
# k = (X - Ai - Bj) / C
# C = 0
#
A=int(input())
B=int(input())
C=int(input())
X=int(input())
sum = 0

for i in range(0,A+1):
    for j in range(0,B+1):
        # Cが固定のパターン
        if C == 0:
            if i*500 + j*100 == X:
                sum+=1
                break
        # Cが不定のパターン
        else:
            k = ( X - i*500 - j*100 ) / 50
            #print (k)
            if k < 0:
                break
            if k<=C:
                sum+=1
        # for k in range(0,C+1):
        #     if(500*i+100*j+50*k==X):

print(sum)
a = input()
n = input()
m = input()
first = a.split(" ")
N = n.split(" ")
M = m.split(" ")
overflow = 0
for i in N:
    if int(i) >= 10**9:
        overflow = 1
        break
        
for i in M:
    if int(i) >= 10**9:
        overflow = 1
        break
if first[0] >= 200000 or first[1] >= 200000:
    overflow = 1
if first[2] >= 10**9:
    overflow = 1
         
if overflow == 0:
    totaltime = 0
    count = 1
    for i in range(int(first[1]) + int(first[0])):
      if i == 6:
        break
      if  len(N) != 0 and len(M) != 0:
        if totaltime + int(N[0]) > int(first[2]) or totaltime + int(M[0]) > int(first[2]):
          break
      if len(N) == 0:
        totaltime += int(M[0])
        M.remove(M[0])
        count += 1
        if totaltime > int(first[2]):
          break
      elif len(M) == 0:
        totaltime += int(N[0])
        N.remove(N[0])
        count += 1
        if totaltime > int(first[2]):
          break
      elif int(N[0]) < int(M[0]):
        totaltime += int(N[0])
        N.remove(N[0])
        count += 1
      elif int(M[0]) < int(N[0]):
        totaltime += int(M[0])
        M.remove(M[0])
        count += 1
    print(count)
else:
    print(0)

### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])
    ans, j = 0, M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
import math

def chmin(a, b):
    if a > b:
        a = b
        return a
    else:
        return a

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

dp = [math.inf] * n
dp[0] = 0

for i in range(1, n):
    dp[i] = chmin(dp[i], dp[i - 1] + abs(ls[i] - ls[i - 1]))
    if i > 1:
        dp[i] =  chmin(dp[i], dp[i - 2] + abs(ls[i] - ls[i - 2]))

print(dp[n - 1])

### FIXED CODE ###

def chmin(a, b):
    if a > b:
        a = b
        return a
    else:
        return a

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

dp = [10**9] * n
dp[0] = 0

for i in range(1, n):
    dp[i] = chmin(dp[i], dp[i - 1] + abs(ls[i] - ls[i - 1]))
    if i > 1:
        dp[i] =  chmin(dp[i], dp[i - 2] + abs(ls[i] - ls[i - 2]))

print(dp[n - 1])
[X,K,D]=list(map(int, input().split()))
n=abs(X)//D
abx=abs(X)
if n>K:
    if X>0:
        ans=X-K*D
    else:
        ans=X+K*D
else:
    x2=abx-n*D
    x1=(n+1)*D-abx
    if x2>=x1:
        if n+1<=K:
            if (K-n-1)%2==0:
                ans=x1
            else:
                ans=x2
    else:
        if (K-n)%2==0:
            ans=x2
        else:
            ans=x1
print(ans) 


### FIXED CODE ###

[X,K,D]=list(map(int, input().split()))
abx=round(abs(X))
n=round(abx//D)
if n>K:
    ans=abx-K*D
else:
    x2=abx-n*D
    x1=(n+1)*D-abx
    if x2>=x1:
        if (K-n-1)%2==0:
            ans=x1
        else:
            ans=x2
    else:
        if (K-n)%2==0:
            ans=x2
        else:
            ans=x1
print(ans)
s = input()
n = len(s)
if n < 4:
  quit()
l,r = 0,4
ans = [[[],[]] for _ in range(n+3)]
for i in range(4,8):
  l = 0
  while l+i <= n:
    if int(s[l:(l+i)])%2019 == 0:
      ans[l+1][0].append(l+i)
      ans[l+i+1][1].append(l+1)
    l += 1
final = 0
cnt = 1
for i in range(n+1):
  if ans[i][0] and ans[i][1]:
    cnt += 1
    final += cnt
  elif ans[i][0]:
    final += 1
    cnt = 1
print(final)

### FIXED CODE ###

s,w = map(int,input().split())
if w >= s:
  print("unsafe")
else:
  print("safe")
a = int(input())
h = int(a / 3600)
m = int(a - h * 3600) / 60
s = int(a - (h * 3600) - (m * 60))
print("%s:%s:%s % (h, m, s)

### FIXED CODE ###

a = int(input())
h = int(a / 3600)
m = int((a - h * 3600) / 60)
s = int(a - (h * 3600) - (m * 60))
print("%s:%s:%s" % (h, m, s))
k

### FIXED CODE ###

from math import pi
r = int(input())
print(2 * pi * r)
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！

def BELLMANFORD(point,n,d,p):
    cost       = [-float("inf")]*(n+1)  #infじゃないと閉路検出がうまくいかない
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p

    negative=[0]*(n+1)                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定 negativeの1は閉路に入っている部分を表す
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now]==1:
                    negative[nex]=1
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    negative[now]=1
 
    return cost,negative

def main():    
    n,m,p=map(int,input().split())

    d={}
    for s in range(m):
        a,b,c=map(int,input().split())
        if a in d:
            d[a].append((b,c))
        else:
            d[a]=[(b,c)]
    
    x,y=(BELLMANFORD(1,d,n,p))
    
    if y[n]==1:
        print(-1)
    else:
        print(max(x[n],0))

    
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline  #危険！基本オフにしろ！


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

d={}
for s in range(m):
    a,b,c=map(int,input().split())
    if a in d:
        d[a].append((b,c))
    else:
        d[a]=[(b,c)]

#print(d)


def BELLMANFORD(point,d,p):
    cost       = [-float("inf") for node in range(n+1)]  #infじゃないと閉路検出がうまくいかない
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p

    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定 negativeの1は閉路に入っている部分を表す
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    negative[now-1]=1
 
    return cost,negative

def main():
    x,y=(BELLMANFORD(1,d,p))
    
    if y[n-1]==1:
        print(-1)
    else:
        print(max(x[n],0))

    
if __name__ == '__main__':
    main()
N = int(input())
A = list(map(int, input().split()))

C = [0 for _ in A]
C[0] = A[0]
for i in range(1, len(A)):
    C[i] = C[i-1] + A[i]

from collections import Counter
from scipy.special import comb
count = Counter(C)

li = list(count.values())

res = 0
for l in li:
    if l == 1:
        pass
    else:
        res += comb(l, 2)
res += count[0]

print(int(res))

### FIXED CODE ###

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

C = [0 for _ in A]
C[0] = A[0]
for i in range(1, len(A)):
    C[i] = C[i-1] + A[i]

from collections import Counter

count = Counter(C)

li = list(count.values())

res = 0
for l in li:
    if l == 1:
        pass
    else:
        res += l * (l - 1) / 2
res += count[0]

print(int(res))
n = int(input())
t = list(map(int, (input().split()))
time = sum(t)
m = int(input())
for i in range(m)
    p, x = map(int, input()/split())
    pritn(time - t[p+1] + x)

### FIXED CODE ###

n = int(input())
t = list(map(int, (input().split())))
T = sum(t)
m = int(input())
for i in range(m):
    p, x = map(int, input().split())
    print(T - t[p-1] + x)
n, m, d = map(int, input().split())
print(((n-d)*(m-1)/n)/(n-1))


### FIXED CODE ###

n, m, d = map(int, input().split())
if d == 0:
    print((m-1)/n)
else:
    print((2*(n-d)/ n**2)*(m-1))
N=int(input())
rest=[]
for i in range(1,N+1):
    s,p=input().split()
    p=int(p)
    rest.append((s,-p,i))


print(x)
for i in range(N):
    print(x[i][2])
    

    


### FIXED CODE ###

N=int(input())
rest=[]
for i in range(1,N+1):
    s,p=input().split()
    p=int(p)
    rest.append((s,-p,i))

x=sorted(rest)


for i in range(N):
    print(x[i][2])
a,b,c,d,e,k = [int,input()] for i range(6)]

print("Yay!" if abs(a-e) <= k else ":(" )

### FIXED CODE ###

a,b,c,d,e,k=[int(input()) for i in range(6)]
print("Yay!" if abs(a-e)<=k else ":(")
a = list(input())
res = 0
for i in range(len(a)+1):
  if a[i] ==1:
    res +=1
print(res)

### FIXED CODE ###

s = input()
res = 0
for v in s:
  res += int(v)
print(res)
N=int(input())
A=list(map(int,input().split()))
ans = 1
if 0 in A:
  print(0)
  return
else:
  for i in range(N):
    ans *= A[i]
    if ans > 10**18:
      print(-1)
      return
  print(ans)


### FIXED CODE ###

def main ():
	N = int(input())
	A = list(map(int,input(). split ()))
	if 0 in A:
		print(0)
		return
	prod = 1
	for a in A:
		prod *= a
		if prod > 1000000000000000000:
			print(-1)
			return
	print(prod)
main ()
N, K = map(int, input().split())
p = []
for i in range(N):
    p.append(int(input()))
p.sort()

price = 0
if N > 0:
    for j in range(3):
        price += p[j]
print(price)

### FIXED CODE ###

N, K = map(int, input().split())
p = [int(x) for x in input().split()]
p.sort()

price = 0
if N > 0:
    for j in range(K):
        price += p[j]
print(price)