Harryxun/stf_run huggingface dataset:
n, m = map(int, input().split())
key_price = [0] * m
box_price = [(-1, [-1])] * (n+1)
box_key = [set([]) for _ in range(n+1)]
for key in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    key_price[key] = a
    for i in c:
        if box_price[i][0] == -1:
            box_price[i] = (a, [key])
        elif box_price[i][0] > a:
            box_price[i] = (a, [key])
        elif box_price[i][0] == a:
            box_price[i] = (a, box_price[i][0] + [key])
        box_key[i].add(key)


def cost(using_keys):
    ret = 0
    for k, v in using_keys.items():
        if v >= 1:
            ret += key_price[k]
    return ret


from collections import defaultdict
keys = defaultdict(int)
kbx = {i: 0 for i in range(1, n+1)}
for i in range(1, n+1):
    if box_price[i][0] == -1:
        print(-1)
        exit()
    keys[box_price[i][1][0]] += 1
    kbx[i] = box_price[i][1][0]

ans = cost(keys)

for key in range(m):
    for i in range(1<<n):
        ks = keys
        kbx1 = kbx
        for b in range(n):
            if i & (1 << b) and key in box_key[b+1]:
                ks[kbx[b+1]] -= 1
                ks[key] += 1
                kbx1[b+1] = key
        tmp = cost(ks)
        if ans > tmp:
            keys = ks
            kbx = kbx1
            ans = tmp

print(ans)



### FIXED CODE ###

n, m = map(int, input().split())
r = [2**i for i in range(n+1)]

price = [0] * m
mask = [0] * m
for i in range(m):
    a, b = map(int, input().split())
    for box in map(int, input().split()):
        mask[i] += r[box-1]
    price[i] = a


inf = 10**9
dp = [[inf] * (1 << n) for _ in range(m+1)]
dp[0][0] = 0
for i in range(m):
    for j in range(1 << n):
        dp[i+1][j | mask[i]] = min(
            dp[i][j] + price[i],
            dp[i+1][j | mask[i]]
        )
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])

ans = dp[m][(1 << n) - 1]
if ans == inf:
    print(-1)
else:
    print(ans)
#a = 314159265
#b = 358979323846264338
a, b = map(int, input().split())
count = 1
x = a
print(x)
while x * 2 <= b:
    x = x * 2
    #print(x)
    count += 1
print(count)

### FIXED CODE ###

a, b, c, d = map(int, input().split())
#a, b, c, d = 3,4,5,2
if a + b > c + d:
    result = "Left"
elif a + b == c + d:
    result = "Balanced"
elif a + b < c + d:
    result = "Right"
print(result)
# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

# ここから処理
s = ns()
k = ni()

chl = list(s)
res = k

for i, c in enumerate(chl):
    if res >= ord("z") - ord(c) + 1:
        chl[i] = "a"
        res -= (ord("z") - ord(c) + 1)

chl[-1] = chr(ord(chl[-1]) + res)

print("".join(chl))

### FIXED CODE ###

# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

# ここから処理
s = ns()
k = ni()

chl = list(s)
res = k

for i, c in enumerate(chl):
    if c == "a":
        continue
    
    elif res >= ord("z") - ord(c) + 1:
        chl[i] = "a"
        res -= (ord("z") - ord(c) + 1)

chl[-1] = chr(ord(chl[-1]) + res%26)

print("".join(chl))
N = int(input())
li = []
for _ in range(N):
    r = int(input())
    li.append(r)
li_uniq = list(set(li))
li_uniq.sort(reverse = True)
Max1 = li_uniq[0]
Max2 = li_uniq[1]
for i in li:
    if i == Max1:
        print(Max2)
    else:
        print(Max1)

### FIXED CODE ###

N = int(input())
li = []
for _ in range(N):
    r = int(input())
    li.append(r)
li_uniq = list(set(li))
li_uniq.sort(reverse = True)
if len(li_uniq) == 1:
    Max1 = li_uniq[0]
    Max2 = li_uniq[0]
else:
    Max1 = li_uniq[0]
    Max2 = li_uniq[1]
if li.count(Max1) > 1:
    for i in li:
        print(Max1)
else:
    for i in li:
        if i == Max1:
            print(Max2)
        else:
            print(Max1)
import numpy as np



N, M = map(int, input().split())
A = np.array(list(map(int, input().split())))
A = A // 2
v = np.lcm.reduce(A)

print((M // v + 1) // 2)





### FIXED CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = list(map(lambda x: int(x) // 2, input().split()))

    X = A[0]
    for i in range(1, N):
        a, b = X, A[i]
        X = a * b // gcd(a, b)
        if X > M:
            print(0)
            exit(0)

    cnt = 0
    tmp = X
    while tmp % 2 == 0:
        tmp = tmp // 2
        cnt += 1
    for a in A:
        if a % (2 ** cnt) == 0 and a % (2 ** (cnt + 1)) != 0:
            continue
        else:
            print(0)
            exit(0)
    print((M // X + 1) // 2)


if __name__ == '__main__':
    main()
a,b=map(int, raw_input().split())

if a > b:
    print "a > b"
elif a < b:
    print "a < b"
else
    print "a == b"

### FIXED CODE ###

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

if a > b:
    print "a > b"
elif a < b:
    print "a < b"
else:
    print "a == b"
input = input()
print(input * input * input)

### FIXED CODE ###

input = int(input())
print(input ** 3)
import sys
sys.setrecursionlimit(100000)

from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

    lcm = lcm_list(A)
    S = 0
    for i in range(N):
        S += lcm // A[i]

    print(round(S % (1e9 + 7)))

main()


### FIXED CODE ###

import sys
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(2147483647)

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

    lcm = lcm_list(A)
    S = 0
    for i in range(N):
        S += lcm // A[i]

    print(round(S % (round(1e9) + 7)))

main()
D, G = map(int,input().split())
num_q = []
bonus = []
for _ in range(D):
	pp,cc = map(int,input().split())
	num_q.append(pp)
	bonus.append(cc)

cnt = [0] * D
ans = float("inf")

def dfs(cnt, i, score):
	global ans

	if sum(cnt) >= ans:
		return True

	if cnt[i] == num_q[i]:
		score += bonus[i]

	if cnt[D-1] == num_q[D-1]:
		if score >= G:
			ans = min([ans,sum(cnt)])
			return True
		else:
			return True

	if score >= G:
		ans = min([ans,sum(cnt)])
		return True
	
	
	for j in range(i,D):
		if cnt[j] < num_q[j]:
			cnt[j] += 1
			dfs(cnt, j, score+(100*(j+1)))
			cnt[j] -= 1

dfs(cnt,0,0)
print(ans)

### FIXED CODE ###

D, G = map(int, input().split())

def Base_10_to_n(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out

p = []
c = []
for _ in range(D):
	p_tmp, c_tmp = map(int,input().split())
	p.append(p_tmp)
	c.append(c_tmp)
t = [(i+1)*100*p[i] + c[i] for i in range(D)]

ans = float("inf")

for i in range(2**D):
	flg = list(map(int, Base_10_to_n(i,2).rjust(D,"0")))
	tmp_score = sum([t[j] for j in range(D) if flg[j] == 1])
	cnt = sum([p[j] for j in range(D) if flg[j] == 1])

	if tmp_score < G:

		rst_max_q = max([j for j in range(D) if flg[j] == 0])

		rst_q_num = 0
		while rst_q_num < p[rst_max_q]:
			tmp_score += 100*(rst_max_q+1)
			rst_q_num += 1
			cnt += 1
			if tmp_score >= G:
				break

		if tmp_score < G:
			continue

	ans = min(ans, cnt)


print(ans)
n,m,k=int(input())
a=list(msp(int,input().split()))
b=list(msp(int,input().split()))
c=0
d=0
e=0
ans=0
while c<=k:
  if a[d]>=b[e]:
    c+=b[e]
    e+=1
    ans+=1
  else:
    c+=a[d]
    d+=1
    ans+=1
if c==k:
  print(ans)
else:
  print(ans-1)

### FIXED CODE ###

n, m, k = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
aa = [0]
bb = [0]
 
for s in range(n):
    aa.append(aa[s] + a[s])
for s in range(m):
    bb.append(bb[s] + b[s])      
ans = 0
j = m
 
for i in range(n+1):
    if aa[i] > k:
        break
    while bb[j] > k - aa[i]:
        j -= 1
    ans = max(ans, i+j)
        
print(ans)
# 累積和
N, K = map(int, input().split())
S = input()

p = '1'
count = 0
cs = []
for c in S:
  if c != p:
    cs.append(count)
    p = c
    count = 1
  else:
    count += 1
cs.append(count)

if len(cs) < 2 * K:
  print(N)

for i in range(1, len(cs)):
  cs[i] += cs[i - 1]

result = cs[2 * K]
for i in range(2, len(cs) - 2 * K, 2):
  t = cs[2 * K + i] - cs[i - 1]
  if t > result:
    result = t
print(result)


### FIXED CODE ###

n, k = map(int, input().split())
s = list(map(int, input()))
j = 1
r = 0
t = []
for i in range(n):
  if s[i] == j:
    r += 1
  else:
    t.append(r)
    r = 1
    j ^= 1
t.append(r)
if j == 0:
  t.append(0)
if k >= (len(t) - 1) // 2:
  print(sum(t))
else:
  result = sum(t[:2 * k + 1])
  j = sum(t[:2 * k + 1])
  i = 2
  while i + 2 * k < len(t):
    j += t[i + 2 * k - 1] + t[i + 2 * k] - (t[i - 2] + t[i - 1])
    result = max(result, j)
    i += 2
  print(result)
# -*- coding: utf-8 -*-

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

P_set = list(set(P))
#print(P_set)
#print(P_set[1])

ans_chk = 0

if ( X < P[0] or X > P[N-1] ):
  print(X)
  ans_chk = 1

if ( ans_chk==0 ):
  for i in range(len(P)):
    if ( P_set[i] == X ):
      X_i = i
      break
    elif ( P_set[i] > X ):
      print(X)
      ans_chk = 1
      break

if ( ans_chk==0 ):
  
  if ( X_i >= N-(X_i+1) ):
    M = N-(X_i+1)
    temp_ans = X + N-(X_i+1) +1
  else:
    M = X_i
    temp_ans = X - X_i -1
  
  for i in range(1,M+1):
    if ( P_set[ X_i -i ] != X-i ):
      print(X-i)
      ans_chk = 1
      break
    elif ( P_set[ X_i +i ] != X+i ):
      print(X+i)
      ans_chk = 1
      break

if ( ans_chk==0 ):
  print(temp_ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

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

if( N == 0 ):
  #print("N=0")
  print(X)

else:
  P = list(map(int,input().split()))
  P_set = list(set(P))
  
  
  ans_chk = 0
  
  if ( X < P_set[0] or X > P_set[N-1] ):
    #print("X < P_set[0] or X > P_set[N-1]")
    print(X)
    ans_chk = 1
  
  if ( ans_chk==0 ):
    for i in range(N):
      if ( P_set[i] == X ):
        X_i = i
        break
      elif ( P_set[i] > X ):
        #print("P_set[i] > X")
        print(X)
        ans_chk = 1
        break
  
  if ( ans_chk==0 ):
    
    if ( X_i > N-(X_i+1) ): # 上の数が少ない → 下は1回多くする
      M = N-(X_i+1)
      temp_ans = X + N-(X_i+1) +1
      #print("temp_ans =",temp_ans)
      
      for i in range(1,M+1):
        if ( P_set[ X_i -i ] != X-i ):
          print(X-i)
          ans_chk = 1
          break
        elif ( P_set[ X_i +i ] != X+i ):
          print(X+i)
          ans_chk = 1
          break
      
      if ( ans_chk==0 ):
        if ( P_set[ X_i -(M+1) ] != X-(M+1) ):
          print( X-(M+1) )
          ans_chk = 1
  
  
    else: # 下の数が少ないor同数 → そのまま
      M = X_i
      temp_ans = X - X_i -1
      #print("temp_ans =",temp_ans)
    
      for i in range(1,M+1):
        if ( P_set[ X_i -i ] != X-i ):
          print(X-i)
          ans_chk = 1
          break
        elif ( P_set[ X_i +i ] != X+i ):
          print(X+i)
          ans_chk = 1
          break
  
  if ( ans_chk==0 ):
    print(temp_ans)
n=int(input())
s=list(input())
t=0
for i in range(n):
    if s[i]=="A" and s[i+1]=="B" and s[i+2]=="C":
        t+=1
print(t)

### FIXED CODE ###

n=int(input())
s=list(input())
t=0
for i in range(n-2):
    if s[i]=="A" and s[i+1]=="B" and s[i+2]=="C":
        t+=1
print(t)
def palindrome(S):
  for i in range(len(S)//2):
#    print(S[i],S[-(i+1)])
    if S[i] != S[-(i+1)]:
      return 0
  return 1
ans = "No"
S = input()
S1 = S[:(len(S)-1)//2]
S1 = S[(len(S)+3)//2:]
if palindrome(S) == 1:
  if palindrome(S1) == 1:
    if palindrome(S2) == 1:
      ans == "Yes"
print(ans)

### FIXED CODE ###

def palindrome(S):
  for i in range(len(S)//2):
#    print(S[i],S[-(i+1)])
    if S[i] != S[-(i+1)]:
      return 0
  return 1
ans = "No"
S = input()
S1 = S[:(len(S)-1)//2]
S2 = S[(len(S)+1)//2:]
#print(palindrome(S))
#print(palindrome(S1))
#print(palindrome(S2))

if palindrome(S) == 1:
  if palindrome(S1) == 1:
    if palindrome(S2) == 1:
      ans = "Yes"
print(ans)
n=int(input())
l=list(map(int,input().split()))
count=0
suml=sum(l)
i=0
while count<suml/2:
    count+=l[i]
    i+=1
k=suml/2
a=l[i]
if count==k:
    print(0)
else:
    print(int(2*(min(count-k,a-count+k))))
    

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
count=0
suml=sum(l)
i=0
while count<suml/2:
    count+=l[i]
    i+=1
k=suml/2
a=l[i-1]
if count==k:
    print(0)
else:
    print(int(2*(min(count-k,a-count+k))))
N = int(input())
a = list(map(int, input().split()))
 
ball = [0] * N
 
 
if a[-1] == 1:
        ball[-1] = 1
 
for i in reversed(range(N-1)):
        tmp = 0
        if i != 0:
                for j in range(i + (i + 1), N, i + 1):
                        #print("i j ", i , j)
                        if (j + 1) % (i + 1) == 0:
                                tmp += ball[j]
        else:
                tmp = ball[1:]
        #print(i+1, tmp, a[i])
        if tmp % 2 != a[i]:
                ball[i] = 1
 
#print(ball)
 
print(sum(ball))
for i in range(N):
        if ball[i] == 1:
                print(i+1, end = " ")

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
 
ball = [0] * N
 
 
if a[-1] == 1:
        ball[-1] = 1
 
for i in reversed(range(N-1)):
        tmp = 0
        if i != 0:
                for j in range(i + (i + 1), N, i + 1):
                        #print("i j ", i , j)
                        if (j + 1) % (i + 1) == 0:
                                tmp += ball[j]
        else:
                tmp = sum(ball[1:])
        #print(i+1, tmp, a[i])
        if tmp % 2 != a[i]:
                ball[i] = 1
 
#print(ball)
 
print(sum(ball))
for i in range(N):
        if ball[i] == 1:
                print(i+1, end = " ")
y, m, d = map( int, input().split("/") )
if m <= 4
   print( "Heisei" )
else : 
   print( "TBD" )

### FIXED CODE ###

y, m, d = map( int, input().split("/") )
if y < 2019 or ( y == 2019 and m <= 4 ) :
   print( "Heisei" )
else : 
   print( "TBD" )
int(input())
l=list(map(int,input().split()))
print('Yes' if max(l)*2< sum(l) else 'No')


### FIXED CODE ###

t,x = map(int,input().split())
print(t/x)
while True:
    n = int(input())
    if n == 0:
        break
    a = [int(input()) for _ in range(n)]
    d = [a[0]]
    for i in range(1, n):
        if a[i] / d[-1] >= 0:
            d[-1] += a[i]
        else:
            d.append(a[i])
    for i in range(2, len(d)):
        if d[i - 1] < 0 and d[i -2] > d[i - 1] and d[i] > d[i - 1]:
            d[i] += d[i -2] + d[i -1]
    print(max(d))



### FIXED CODE ###

from collections import deque
while True:
    n = int(input())
    if n == 0:break
    a = [int(input()) for _ in range(n)]
    b = deque([0] * n)
    j = 0
    for i in range(n):
        if a[i] * b[j] >= 0:b[j] += a[i]
        else:j += 1;b[j] += a[i]
    if b[0] < 0 and len(b) > 1:b.popleft()
    while b[-1] <= 0 and len(b) > 1:b.pop()
    if len(b) == 1 and b[0] <= 0:print(max(a))
    else:
        m = len(b) // 2 + 1
        v = [[0] * m for _ in range(m)]
        v[0][0] = b[0]
        for i in range(1, m):
            v[0][i] = v[0][i - 1] + b[2 * i] + b[2 * i - 1]
        for i in range(1, m):
            for j in range(i, m):
                v[i][j] = v[i - 1][j] - b[2 * i - 2] - b[2 * i - 1]
        print(max([max(i) for i in v]))
n = input()
A = {}
for i in xrange(2, n+1):
    v = int(raw_input())
    A.setdefault(v, []).append(i)
f = lambda v: (v in A)/1 and 1+max(e+i for i,e in enumerate(sorted(map(f,A[v]))[::-1]))
print f(1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n = input()
A = {}
for i in xrange(2, n+1):
    v = int(raw_input())
    A.setdefault(v, []).append(i)
f = lambda v: (v in A)/1 and 1+max(e+i for i,e in enumerate(sorted(map(f,A[v]))[::-1]))
print f(1)
H,W = map(int,input().split(' '))
S = []
for i in [0]*H:
	l = input()
	S.append([1 if x == '#' else -1 for x in l])

def check(S,x,y):
	global bk
	global wh
	if S[y][x] == 0:
		return
	if S[y][x] == 1:
		bk += 1
		S[y][x]=0
		if 0 < y and S[y-1][x] == -1:
			check(S,x,y-1)
		if 0 < x and S[y][x-1] == -1:
			check(S,x-1,y)
		if y < H-1 and S[y+1][x] == -1:
			check(S,x,y+1)
		if x < W-1 and S[y][x+1] == -1:
			check(S,x+1,y)
	else:
		wh += 1
		S[y][x]=0
		if 0 < y and S[y-1][x] == 1:
			check(S,x,y-1)
		if 0 < x and S[y][x-1] == 1:
			check(S,x-1,y)
		if y < H-1 and S[y+1][x] == 1:
			check(S,x,y+1)
		if x < W-1 and S[y][x+1] == 1:
			check(S,x+1,y)
	return

cnt = 0
bk = 0
wh = 0
for y in range(H):
	for x in range(W):
		if S[y][x] == 1:
			check(S,x,y)
			cnt += wh*bk
			wh = 0
			bk = 0
print(cnt)




### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

H,W = map(int,input().split(' '))
S = []
for i in [0]*H:
	l = input()
	S.append([1 if x == '#' else -1 for x in l])

bk = 0
wh = 0
def check(S,x,y):
	global bk
	global wh
	if S[y][x] == 0:
		return
	if S[y][x] == 1:
		bk += 1
		S[y][x]=0
		if 0 < y and S[y-1][x] == -1:
			check(S,x,y-1)
		if 0 < x and S[y][x-1] == -1:
			check(S,x-1,y)
		if y < H-1 and S[y+1][x] == -1:
			check(S,x,y+1)
		if x < W-1 and S[y][x+1] == -1:
			check(S,x+1,y)
		return
	if S[y][x] == -1:
		wh += 1
		S[y][x]=0
		if 0 < y and S[y-1][x] == 1:
			check(S,x,y-1)
		if 0 < x and S[y][x-1] == 1:
			check(S,x-1,y)
		if y < H-1 and S[y+1][x] == 1:
			check(S,x,y+1)
		if x < W-1 and S[y][x+1] == 1:
			check(S,x+1,y)
		return

cnt = 0
for y in range(H):
	for x in range(W):
		if S[y][x] == 1:
			check(S,x,y)
			cnt += wh*bk
			wh = 0
			bk = 0
print(cnt)
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    if w % 2 == 0:
        graph[u].append((v, 1))
        graph[v].append((u, 1))
    else:
        graph[u].append((v, -1))
        graph[v].append((u, -1))
            
color = [None for i in range(n)]
def set_color(v, c):
    color[v] = c
    for next_v, d in graph[v]:
        if color[next_v] is None:
            set_color(next_v, d * c)

set_color(0, 1)
for c in color:
    if c != 1:
        print(0)
    else:
        print(1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    if w % 2 == 0:
        graph[u].append((v, 1))
        graph[v].append((u, 1))
    else:
        graph[u].append((v, -1))
        graph[v].append((u, -1))
            
color = [None for i in range(n)]
def set_color(v, c):
    color[v] = c
    for next_v, d in graph[v]:
        if color[next_v] is None:
            set_color(next_v, d * c)

set_color(0, 1)
for c in color:
    if c != 1:
        print(0)
    else:
        print(1)
N,K=map(int, input().split())
if N % K = 0:
 print(0)
else:
 print(1)

### FIXED CODE ###

N,K=map(int, input().split())
if N % K == 0:
 print(0)
else:
 print(1)
from scipy.sparse.csgraph import dijkstra, bellman_ford, csgraph_from_dense, NegativeCycleError
from itertools import permutations

INF = float("inf")

N, M, P, *ABC = map(int, open(0).read().split())

D = [[0] * N for _ in range(N)]
for a, b, c in zip(*[iter(ABC)] * 3):
    D[a - 1][b - 1] = c

T = dijkstra(D)

E = [[0] * N for _ in range(N)]
for a, b, c in zip(*[iter(ABC)] * 3):
    if T[b - 1][N - 1] < INF:
        E[a - 1][b - 1] = P - c

try:
    G = bellman_ford(csgraph_from_dense(E), indices=0)
    ans = max(0, -int(G[N - 1]))
except NegativeCycleError:
    ans = -1

print(ans)


### FIXED CODE ###

def main():
    INF = float("inf")

    N, M, P, *ABC = map(int, open(0).read().split())

    F = [[] for _ in range(N)]
    B = [[] for _ in range(N)]
    E = [(a - 1, b - 1, P - c) for a, b, c in zip(*[iter(ABC)] * 3)]

    for a, b, c in E:
        F[a].append(b)
        B[b].append(a)

    S = {0}
    stack = [0]
    while stack:
        s = stack.pop()
        for v in F[s]:
            if v not in S:
                stack.append(v)
                S.add(v)

    T = {N - 1}
    stack = [N - 1]
    while stack:
        s = stack.pop()
        for v in B[s]:
            if v not in T:
                stack.append(v)
                T.add(v)

    ok = S & T

    D = [INF] * N
    D[0] = 0

    def bellman_ford(N):
        for _ in range(N):
            update = False
            for a, b, c in E:
                if a in ok and b in ok and D[b] > D[a] + c:
                    D[b] = D[a] + c
                    update = True
            if not update:
                return False
        return True

    bellman_ford(N)

    print(-1 if bellman_ford(1) else max(-D[-1], 0))



if __name__ == '__main__':
    main()
while True:
  x = int(input().split())
  if x == 0:
    break
  print("Case ", c, ": ", x, sep="")
  c += 1    # c = c + 1 の略記法


### FIXED CODE ###

c = 1
while True:
  x = int(input())
  if x == 0:
    break
  print("Case ", c, ": ", x, sep="")
  c += 1    # c = c + 1 の略記法
#ABC116D-VariousSushi.py

import sys
import numpy as np
from operator import itemgetter

input = sys.stdin.readline

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
List1, List2 = [], []
Score= 0
kind = []

for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    if INPUT2[0] not in kind and len(List1) <= K:
        List1.append(INPUT2[1])
        kind.append(INPUT2[0])
    elif INPUT2[0] in kind:
        List2.append(INPUT2[1])

List1.sort(reverse=True)
List2.sort()

kindnumber = len(List1)
k = len(List2)-(K-kindnumber)

Score = np.sum(List1) + np.sum(List2[k:]) + kindnumber ** 2
del List2[k:]
Test = Score

for i in range(kindnumber):
    Test = Test - List1.pop() + List2.pop() - 2 * kindnumber + 1
    kindnumber = kindnumber - 1
    if Test >= Score:
        Score = Test
    if List2 == []:
        break

print(int(Score))


### FIXED CODE ###

#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

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

INPUT.sort(key = lambda x: -x[1])

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)
temp = []
a,b,k = map(int,input().split())
for i in range (1, min(a,b)):
  if a%i==0 and b%i==0:
    temp.append(i)
print(temp[-k])

### FIXED CODE ###

temp = []
a,b,k = map(int,input().split())
for i in range (1, min(a,b)+1):
  if a%i==0 and b%i==0:
    temp.append(i)
print(temp[-k])
s = ''.join(input().split('/'))
if s>20190430:
    print("TBD")
else:
    print("Heisei")

### FIXED CODE ###

Y, M, D = map(str, input().split("/"))
s = ''.join([Y,M,D])

if int(s)>20190430:
    print("TBD")
else:
    print("Heisei")