Harryxun/stf_run huggingface dataset:
def merge_jibun(A, left, mid, right):
    global count
    # inf = 10 ** 9
    L = A[left:mid] + [10 ** 4]
    R = A[mid:right] + [10 ** 4]
    # L.append(1000000)
    # R.append(1000000)

    i = 0
    j = 0
    
    
    for k in range(left, right):
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def merge_hoka(A, left, mid, right):
    global count
    inf = 10 ** 9
    L = A[left:mid] + [inf]
    R = A[mid:right] + [inf]
 
    i = 0
    j = 0
    for k in range(left, right):
        count += 1
        # print(L)
        # print(R)
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge_jibun(A, left, mid, right)
        # merge_hoka(A, left, mid, right)

n = int(input())
A = list(map(int, input().split()))
count = 0
mergeSort(A, 0, n)

print(' '.join(list(map(str, A))))
print(count)


### FIXED CODE ###

def merge(A, left, mid, right):
    global count
    inf = 10 ** 9
    L = A[left:mid] + [inf]
    R = A[mid:right] + [inf]

    i = 0
    j = 0
    for k in range(left, right):
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

n = int(input())
A = list(map(int, input().split()))
count = 0
mergeSort(A, 0, n)

print(' '.join(list(map(str, A))))
print(count)
import sys
sys.setrecursionlimit(10000000)

n = int(input())
x = input()

c1 = x.count('1')
cc1 = int('0b' + x, 0) % (c1 - 1)
cc2 = int('0b' + x, 0) % (c1 + 1)

def f(n):
    ans = 0
    while n > 0:
        ans += 1
        n = n % bin(n).count('1')
    return ans

for i in range(n):
    if x[i] == '1':
        print(f((pow(2, n-i-1, c1-1) + cc1) % (c1 - 1)) + 1)
    else:
        print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

n = int(input())
x = input()

c1 = x.count('1')
if c1 > 1:
    cc1 = int('0b' + x, 0) % (c1 - 1)
cc2 = int('0b' + x, 0) % (c1 + 1)

def f(n):
    ans = 0
    while n > 0:
        ans += 1
        n = n % bin(n).count('1')
    return ans

if c1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)
    exit()

for i in range(n):
    if x[i] == '1':
        print(f((-pow(2, n-i-1, c1-1) + cc1) % (c1 - 1)) + 1)
    else:
        print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)
S = input()
T = input()
hit = 0
for i in range(3):
    if S[i] == T[i]:
        hit = hit + 1
print(hit)

### FIXED CODE ###

S = input()
if S[2]==S[3] and S[4]==S[5]:
    print("Yes")
else:
    print("No")
s=input()
for i in range(len(s)//2+1):
  if s[2*i]!='R' and s[2*i]!='U' and s[2*i]!='D' :
    print('No')
    exit()
  if s[2*i+1]!='L' and s[2*i+1]!='U' and s[2*i+1]!='D':
    print('No')
    exit()
if 
print('Yes')


### FIXED CODE ###

s=input()
if len(s)%2==0:
  for i in range(len(s)//2):
    if s[2*i]!='R' and s[2*i]!='U' and s[2*i]!='D' :
      print('No')
      exit()
    if s[2*i+1]!='L' and s[2*i+1]!='U' and s[2*i+1]!='D':
      print('No')
      exit()
if len(s)%2==1:
  for i in range(len(s)//2):
    if s[2*i+1]!='L' and s[2*i+1]!='U' and s[2*i+1]!='D':
      print('No')
      exit()
  for i in range(len(s)//2+1):
    if s[2*i]!='R' and s[2*i]!='U' and s[2*i]!='D' :
      print('No')
      exit()
print('Yes')
N = int(input()) #1行目のNを取得する
s_char = list(input().split())
s = [int(n) for n in s_char]
ans = 1

for num in s:
    if len(str(ans))+len(str(num))>20:
        #print('e')
        ans = -1
        break
    ans *= num
    if ans > 10**18:
        ans = -1
        break

for num in s:
    if num == 0:
        ans = 0
        
print(ans)

### FIXED CODE ###

s = input().split()
print(int(s[0])*int(s[1]))
n = int(input())

print("ABC" + n)


### FIXED CODE ###

n = int(input())

print("ABC" + str(n))
n = int(input())
a = n.find("7")
if a>-1:
  print("Yes")
else :
  print("No")

### FIXED CODE ###

n = int(input())
a = str(n).find("7")
if a>-1:
    print("Yes")
else :
    print("No")
s = input()
k = int(input())
infinity = 5 * (10 ** 15) - 1

import math

i = 0
while k > 0:
  
  k -= math.floor(infinity * math.log(int(s[i]), 10)) + 1
  i += 1
  
print(s[i-1])


### FIXED CODE ###

s = input()
k = int(input())

for i in map(int, s[:k]):
  if i != 1:
    print(i)
    break
else:
  print(1)
all = input()
if sum(all) >=22:
  return 'bust'
else:
  return 'win'

### FIXED CODE ###

all = input()
all = all.split(' ')
all = [int(num) for num in all]
if sum(all) >= 22:
    print('bust')
else:
    print('win')
def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime

def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime

pl = eratosthenes(10**6)
pd = {}
for p in pl:
    pd[p] = 0

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

A.sort()
d = {}
ans = 0
for i in range(N):
    if A[i] not in pd:
        primes = prime_decomposition(A[i])
        for p in primes:
            if p not in d:
                d[p] = 0
            else:
                ans = 1

if ans == 0:
    print('pairwise coprime')
else:
    def gcd(a, b):
    	while b:
    		a, b = b, a % b
    	return a
    a = A[0]
    for i in range(N):
        a = gcd(a,A[i])
    if a==1:
        print('setwise coprime')
    else:
        print('not coprime')

### FIXED CODE ###

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

def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

A.sort()
M = A[-1]
d = {}
ans = 0

for i in range(N):
    if A[i] not in d:
        primes = prime_decomposition(A[i])
        for p in primes:
            for j in range(1,M//p+1):
                d[j*p] = 0
    else:
        ans = 1
        break
if ans == 0:
    print('pairwise coprime')
else:
    def gcd(a, b):
    	while b:
    		a, b = b, a % b
    	return a
    a = A[0]
    for i in range(N):
        a = gcd(a,A[i])
    if a==1:
        print('setwise coprime')
    else:
        print('not coprime')
N = int(input())
s = list(input())

ans = 0
for i in range(len(s)-1):
    if s[i] !== s[i+1]:
        ans += 1
    else:
        ans = ans

ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
s = list(input())
ans = 0
for i in range(len(s)-1):
    if s[i] != s[i+1]:
        ans += 1
    else:
        ans = ans
ans += 1
print(ans)
from collections import Counter
from functools import reduce
n, *S = open(0).read().split()
keys = reduce(and_, map(set, S))
d = {c:10**6 for c in keys}
for counter in map(Counter, S):
    for c in keys:
        if c in counter:
            d[c] = min(d[c], counter[c])
ans = ''
for k, v in sorted(d.items()):
    ans += k * v
print(ans)

### FIXED CODE ###

from collections import Counter
from functools import reduce
from operator import and_
n, *S = open(0).read().split()
keys = reduce(and_, map(set, S))
d = {c:10**6 for c in keys}
for counter in map(Counter, S):
    for c in keys:
        if c in counter:
            d[c] = min(d[c], counter[c])
ans = ''
for k, v in sorted(d.items()):
    ans += k * v
print(ans)
N, K = input().strip().split()
h = list(map(int, input().split()))
count = 0

for i in h:
    if i >= K:
        count += 1
print(count)

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
count = [i for i in h if i >= K]
print(len(count))
import math

def make_plist(n):
	sqrt = int(math.sqrt(n))
	plist = [1]*(sqrt+3)
	plist[0] = 0
	for i in range(2,int(math.sqrt(sqrt))+2):
		if plist[i]:
			plist[2*i::i] = [0 for x in range(2*i,sqrt+3,i)]
	return plist

def get_pfact(plist,n):
	pfact = []
	sqrt = int(math.sqrt(n))
	for i in range(2,sqrt+1):
		if plist[i] and n%i == 0:
			pfact.append(i)
	if p[n] == 1: pfact.append(n)
	return pfact

def get_phai(n,pfacts):
	phai = n
	for pfact in pfacts:
		phai *= (1-1/float(pfact))
	return int(phai)

# main	
n = int(raw_input())
plist = make_plist(n)
pfacts = get_pfact(plist,n)
print get_phai(n,pfacts)

### FIXED CODE ###

def phi(n):
	r = n
	i = 2
	while i*i <= n:
		if n%i==0:
			r -= r/i
			while n%i==0:
				n /= i
		i += 1
	if n>1: r-= r/n
	return r

n = int(raw_input())
print phi(n)
def i():
    return int(input())
def i2():
    return map(int,input().split())
def s():
    return str(input())
def l():
    return list(input())
def intl():
    return list(int(k) for k in input().split())

n,m=i2()
h=intl()
cnt=0
score=0
l=[[] for i in range(n)]
for j in range(m):
	a,b=i2()
	l[a-1].append(b-1)
	l[b-1].append(a-1)
for j in range(n):
	for k in l[j]:
		if h[j]>h[k]:
			cnt+=1
			if cnt==len(l[j]):
				score+=1
	cnt=0
for i in range(m):
	if len(l[i])==0:
		score+=1
print(score)

### FIXED CODE ###

def i():
    return int(input())
def i2():
    return map(int,input().split())
def s():
    return str(input())
def l():
    return list(input())
def intl():
    return list(int(k) for k in input().split())

n,m=i2()
h=intl()
cnt=0
score=0
l=[[] for i in range(n)]
for j in range(m):
	a,b=i2()
	l[a-1].append(b-1)
	l[b-1].append(a-1)
for j in range(n):
	for k in l[j]:
		if h[j]>h[k]:
			cnt+=1
			if cnt==len(l[j]):
				score+=1
	cnt=0
for i in range(n):
	if len(l[i])==0:
		score+=1
print(score)
while True:
    [W, H] = raw_input().split()
    if [W, H] == [0, 0]:
        break
    print('#' * W)
    counter = 0
    while counter < H - 1:
        print('#' + '.' * (W - 2) + '#')
    print('#' * W)

### FIXED CODE ###

while True:
    [H, W] = [int(x) for x in raw_input().split()]
    if [H, W] == [0, 0]:
        break
    print('#' * W)
    counter = 0
    while counter < H - 2:
        print('#' + '.' * (W - 2) + '#')
        counter += 1
    print('#' * W + '\n')
n, k = map(int,input().split())
if (K == 1):
    print(0)
else:
    print(n - k)

### FIXED CODE ###

n, k = map(int,input().split())
if (k == 1):
    print(0)
else:
    print(n - k)
N, K = map(int, input().split())
H = [int(input()) for _ in range(N)]

H.sort(reverse=True)

min_score = pow(10, 9)
for i in range(N - K + 1):
    min_score = min(min_score, H[i] - H[i + K - 1])

print(min_score)



### FIXED CODE ###

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

H.sort(reverse=True)

min_score = pow(10, 9)
for i in range(N - K + 1):
    min_score = min(min_score, H[i] - H[i + K - 1])

print(min_score)
import numpy as np

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

suma=np.sum(A)
remain=N-suma
       
if remain>=0:
       print(remain)
else:
       print('-1')


### FIXED CODE ###

import numpy as np

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

suma=np.sum(A)
remain=N-suma

if remain>=0:
	print(remain)
else:
	print(-1)
import numpy as np
l,r = map(int, input().split())
arr1 = np.array(range(l,r+1))
arr2 = np.array(range(l,r+1)).reshape(r-l+1,1)
arr = arr1*arr2%2019
for i in range(r-l+1):
  arr[i][i] = 2019
print(np.min(arr))

### FIXED CODE ###

import numpy as np
l,r = map(int, input().split())
if ((l//2019)<(r//2019)):
  print(0)
else:
  arr1 = np.array(range(l,r+1))
  arr2 = np.array(range(l,r+1)).reshape(r-l+1,1)
  arr = arr1*arr2%2019 + (np.identity(r-l+1)*2019)
  print(int(np.min(arr)))
import numpy as np
import sys
f = [-1 for i in range(45)]
f[0] = f[1] = 1

def fib(n):
    global f
    for i in range(2,n+1):
        f[i] = f[i - 1] + f[i - 2]
        #print(i,f[i])
    return f[n]

if __name__ == "__main__":
    n = input("input number: ")
    n = int(n)
    #print(type(n))
    print(fib(n))



### FIXED CODE ###


f = [-1 for i in range(45)]
f[0] = f[1] = 1

def fib(n):
    global f
    for i in range(2,n+1):
        f[i] = f[i - 1] + f[i - 2]
        #print(i,f[i])
    return f[n]

if __name__ == "__main__":
    n = input()
    n = int(n)
    #print(type(n))
    print(fib(n))
import numpy as np

n = int(input())

num = np.zeros(10 ** 9, dtype = bool)

for i in range(n):
    a = int(input())

    num[a] = not(num[a])

sum = np.where(num == True) 

print(len(sum[0]))

### FIXED CODE ###

import numpy as np

n = int(input())

a = np.zeros(n, dtype = int)

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

a = np.sort(a)

sum = 0
for i in range(n):
    if(i == 0):
        flag = 1
    elif(a[i - 1] == a[i]):
        flag += 1
    else:
        if(flag % 2 == 1):
            sum += 1
        else:
            flag = 1

if(flag % 2 == 1):
    sum += 1

print(sum)
import math
from operator import mul
from functools import reduce
def get_primenumber(number):#エラトステネスの篩
    prime_list = []
    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
    while search_list[0] <= math.sqrt(number):
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        search_list = [num for num in search_list if num % head_num != 0]
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list

n = int(input())
plist = get_primenumber(n)
result = 0
for i in range(1, n+1):
    templ = [1]
    i1 = i
    for j in plist:
        if(j == i):
            templ.append(2)
            break
        elif(i % j == 0):
            temp = 1
            while(i % j == 0 and i != j):
                
                i = int(i / j)
                temp += 1
            if(i == j):
                temp +=1
            templ.append(temp)
    result += reduce(mul, templ) * i1
print(result)
        

### FIXED CODE ###

n = int(input())
result = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        if(i * j <= n):
            result += i*j
        else:
            break
print(result)
line = input().split(" ")
a = list(map(int, line))
data = [0]*90000
ans=0
for i in range(0, a[0]):
    line = input().split(" ")
    temp = list(map(int, line))
    for j in range(0, a[1]):
        data[temp[j]] = [i,j]
times=int(input())
for i in range(0,times):
    line = input().split(" ")
    temp = list(map(int, line))
    nowloc=temp[0]
    ans=0
    while nowloc!=temp[1]:
        ans+=abs(data[nowloc][0]-data[nowloc+a[2]][0])+abs(data[nowloc][1]-data[nowloc+a[2]][1])
        nowloc+=a[2]
    print(ans)

### FIXED CODE ###

line = input().split(" ")
a = list(map(int, line))
data = [0] * 90001
ans = 0
for i in range(0, a[0]):
    line = input().split(" ")
    temp = list(map(int, line))
    for j in range(0, a[1]):
        data[temp[j]] = [i, j]

memo = [0] * 90001

for i in range(1, a[0] * a[1]+1):
    if i < a[2]+1:
        memo[i] = 0
    else:
        memo[i] = memo[i - a[2]] + abs(data[i][0] - data[i - a[2]][0]) + abs(data[i][1] - data[i - a[2]][1])
times = int(input())
for i in range(0, times):
    line = list(map(int, input().split(" ")))
    print(memo[line[1]] - memo[line[0]])
n = int(input())
temp_word = [input() for i in range(n)]
word = str(temp_word)

num = int(n / 2)
if word[:num] == word[num:] :
	print("Yes")
else :
	print("No")


### FIXED CODE ###

n = int(input())
word = str(input())

num = int(n / 2)
if word[:num] == word[num:] :
	print("Yes")
else :
	print("No")
import sys
import numpy as np
import math
from collections import deque 
from functools import reduce

# input = sys.stdin.readline

x, y = map(int, input().split())

if (y == 0):
  print(x)
  exit()

p = [list(map(int, input().split()))]
p_n = np.array(p)
p_n = p_n.reshape(-1)
pp = np.arange(1, 100)
for i in p_n:
    pp[i-1] = 10000
sa = min(abs(pp-x))
if pp[x-sa-1] == 10000:
    print(x+sa)
else:
    print(x-sa)

### FIXED CODE ###

import sys
import numpy as np
import math
from collections import deque 
from functools import reduce

# input = sys.stdin.readline
x, y = map(int, input().split())
if y == 0:
    print(x)
    exit()
p = [list(map(int, input().split()))]
p_n = np.array(p)
p_n = p_n.reshape(-1)
pp = np.arange(0, 102)
for i in p_n:
    pp[i] += 10000
sa = min(abs(pp-x))
if sa <= 101:
    if pp[x-sa] >= 10000:
        print(x+sa)
    else:
        print(x-sa)
else:
    print("0")
n = int(input())
v = list(sorted(map(int, input().split())))

counts = {}
x = v[0]
c = 0
for i in v:
    if i != x:
        counts[x] = c
        x = i
        c = 0
    c += 1
counts[x] = c

v1 = list(counts)

sums = [0]
for i in range(1, 1005):
    try:
        sums.append(v1.index(i))
    except ValueError:
        sums.append(sums[-1])


total = 0
for i, x in enumerate(v1[:n-2]):
    if x == 1:
        continue
    for j, y in enumerate(v1[i+1:n-1]):
        total += (sums[min(1004, x+y-1)] - sums[y])



for i, c in counts.items():
    if c >= 2:
        total += (sums[min(1004, 2*i-1)] - sums[c])





# v3
total += sum(True if c >= 3 else False for c in counts.values())


print(total)

### FIXED CODE ###

n = int(input())
v = list(sorted(map(int, input().split())))
v.append(2000)
total = n*(n-1)*(n-2) / 6



def bs(left, s):
    right = n+1
    while left < right-1:
        m = (right+left)//2

        if v[m]>=s:
            right = m
        else:
            left = m
    return left+1






for i, x in enumerate(v[:-2]):
    for j, y in enumerate(v[i+1:-1]):
        k = bs(j+1, y+x)
        total -= (n-k)

print(int(total))
A,B,X = map(int,input().split())
print(min(B-1,N))

### FIXED CODE ###

A,B,N = map(int,input().split())
x = min(B-1,N)
ans = int(A*x/B) - A*int(x/B)
print(ans)
r = map(int,input().split())
print (format(r**r*3.14159265, '.6f'),format(r*r*3.14159265, '.6f'))

### FIXED CODE ###

from math import pi
r = float(input())
print (format(r**2*pi, '.6f'),format(r*pi*2, '.6f'))
import math
A,B,C,D = map(int, input().split())

nrofC = (B // C) - ((A-1) // C)
nrofD = (B // D) - ((A-1) // D)

cdlcm = C * D // math.gcd(C,D)
nrofCD = (B // cdlcm) - ((A-1) // cdlcm)

print((B-(A-1)) - nrofC - nrofD + nrofCD)


### FIXED CODE ###

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

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

nrofC = (B // C) - ((A-1) // C)
nrofD = (B // D) - ((A-1) // D)

cdlcm = (C * D) // gcd(D,C)
nrofCD = (B // cdlcm) - ((A-1) // cdlcm)

print((B-(A-1)) - nrofC - nrofD + nrofCD)
a=list(map(int,input().split()))
def cud(a,b):
  if a%b==0:
    return a/b
  else:
    cud(b,a%b)
print(a*b/cud(a[0],a[1]))

### FIXED CODE ###

a=list(map(int,input().split()))
def cud(a,b):
  if a%b==0:
    return b
  else:
    return cud(b,a%b)
print(int(a[0]*a[1]/cud(a[0],a[1])))
x, y = map(int, input().split())
a = x
i = 0
al.append(a)
while (a < y):
  a *= 2
  i += 1
  if a >= y:
    break
print(i)

### FIXED CODE ###

x, y = map(int, input().split())
a = x
i = 1
while (a <= y):
  a *= 2
  if a > y:
    break
  i += 1
print(i)
s = input()

l = len(s)

if l % 2 == 1:
    print("No")
else:
    for i in range(0, l, 2):
        if s[i:i+2] == "hi":
            continue
        else:
            print("No")
            return
    print("Yes")

### FIXED CODE ###

s = input()
 
l = len(s)
 
if l % 2 != 0:
    print("No")
else:
    for i in range(0, l, 2):
        if s[i:i+2] == "hi":
            if i == l-2:
                print("Yes") 
            else:
                continue

        else:
            print("No")
            break
n, m, c = map(int,input().split())
B = list(map(int,input().split()))
A = [input().split() for l in range(n)]
cnt = 0
for i in range(n):
    sum = 0
    for j in range(m):
        sum += int(A[i][j]) * B[j]
    if sum + c > 0:
        cnt += 1
print(cnt)


### FIXED CODE ###

H, W = map(int, input().split())
h, w = map(int, input().split())

white_cells_int = H * W - ((h * W) + (w * H) - (h * w))
print(str(white_cells_int))
s = input()
k = int(input())
ans = 0
space = 0
while (i < len(s)):
  if s[i] == s[i + 1]:
	ans += 1
    i += 2
  else:
    i += 1
if s[-1] == s[0]:
  space = 1
final_ans = (ans * k) + (space * (k - 1))
print(final_ans)

### FIXED CODE ###

s = input()
k = int(input())
count = []
now = 1
for i in range(len(s) - 1):
    if s[i] == s[i + 1]:
        now += 1
    else:
        count.append(now)
        now = 1
count.append(now)
if len(count) == 1:
    ans = (count[0] * k) // 2
else:
    if s[0] == s[-1]:
        temp = 0
        for i in count:
            temp += i // 2
        ans = (temp * k) - ((count[0] // 2) + (count[-1] // 2)  - ((count[0] + count[-1]) // 2)) * (k - 1)
    else:
        ans = sum([c // 2 for c in count]) * k
print(ans)
a, b, c, d = map(int, input().split())

train = [a,b]
bus = [c,d]

print(train + bus)

### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
D = int(input())

train = [A,B]
bus = [C,D]

print(min(train) + min(bus))
from collections import defaultdict
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(int)
c=0
d=0
e=0
for i in range(N):
 A,B = map(int,input().split())
 if A==0 or B==0:
  e+=1
 else:
  dic[Fraction(A,B)]+=1
ans=1
for k in dic:
 if -1/k in dic:
  ans*=(pow(2,dic[k],mod)+pow(2,dic[-1/k],mod) -1)
  ans%=mod
  dic[k]=0
  dic[-1/k]=0
 else:
  ans*=pow(2,dic[k],mod)
  ans%=mod
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)


### FIXED CODE ###

N=int(input())
if N%10==3:
 print("bon")
elif N%10==0 or N%10==1 or N%10==6 or N%10==8:
 print("pon")
else:
 print("hon")
s = input()
if s[:4] == 2019 and s[5] == 0 and s[6] <= 4 or s[:4] < 2019:
  print("Heisei")
else:
  print("TBD")

### FIXED CODE ###

s = input()
 
if s <= '2019/04/30':
    print('Heisei')
else:
    print('TBD')
from collections import deque

n, m, p = map(int, input().split())
edge = [[] for _ in range(n)]
coin = [[0]*n for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    coin[a][b] = c - p


visited = [0] * n
def dfs(v):
    for u in edge[v]:
        if visited[u] == 0:
            visited[u] = 1
            dfs(u)
visited[0] = 1
dfs(0)
# print(visited)
flag = [vi for vi in visited]

def dfs2(v):
    for u in edge[v]:
        if u == n - 1:
            visited2[u] = 1
            break
        if visited2[u] == 0:
            visited2[u] = 1
            dfs2(u)
for i in range(1, n):
    visited2 = [0] * n
    visited2[i] = 1
    dfs2(i)
    if visited2[n-1] == 0 and flag[i] == 1:
        flag[i] = 0

# print(flag)
target_v = set([i for i in range(n) if flag[i] == 1])
# print(target_v)

q = deque()
q.append((0, 0))
visited3 = [0] * n
visited3[0] = 1
ans = [0] * n
iter = 0
impossible = False
while q:
    v, c = q.popleft()
    for u in edge[v]:
        if u not in target_v:
            continue
        if visited3[u] == 0:
            ans[u] = c + coin[v][u]
            visited3[u] = 1
            q.append((u, c + coin[v][u]))
        else:
            if ans[u] <= c + coin[v][u]:
                impossible = True
                break

    if impossible:
        break

if impossible:
    print(-1)
else:
    print(max(0, ans[n-1]))


### FIXED CODE ###

n, m, p = map(int, input().split())
graph = [[] for _ in range(n)]
edge = []
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append((b, -c+p))
    edge.append((a, b, -c+p))

INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n):
    for v_from, v_to, cost in edge:
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            d[v_to] = d[v_from] + cost

exist = True
for i in range(n):
    for v_from, v_to, cost in edge:
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            d[v_to] = d[v_from] + cost
            if v_to == n - 1:
                exist = False

if not exist:
    print(-1)
else:
    print(max(0, -d[n-1]))