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

n,k = map(int, input().split())
a = list(map(int, input().split()))

nums = [0]*n
for i in range(n-k+1):
  nums[k+i-1] = sum(a[i:k+i])

for i in range(k,n):
  if nums[i-1] < nums[i]: print("Yes")
  else: print("No")

### FIXED CODE ###

n,k = map(int, input().split())
a = list(map(int, input().split()))

nums = [0]*n
nums[k-1] = sum(a[:k])
for i in range(k,n):
  nums[i] = nums[i-1] + a[i] - a[i-k]

for i in range(k,n):
  if nums[i-1] < nums[i]: print("Yes")
  else: print("No")
### BUGGY CODE ###

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
MOD = 10**9 + 7

I = [ [ j for j in range(N) if Ai[j]] for Ai in A ]

memo = [-1]*(1<<N)
memo [0] = 1

def dfs(S,c ) :
    if memo[S] != -1:
        return memo[S]

    r = 0
    for i in I[c]: # bit count
        if S & (1<<i):
            r += dfs(S ^ (1<<i), c+1)
    memo[S] = r = r %MOD
    return r
print(dfs((1<<N)-1,0))


### FIXED CODE ###

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
MOD = 10**9 + 7

I = [ [ j for j in range(N) if Ai[j]] for Ai in A ]

memo = [-1]*(1<<N)
memo [0] = 1

def dfs(S,c ) :
    if memo[S] != -1:
        return memo[S]

    r = 0
    for i in I[c]: # bit count
        if S & (1<<i):
            r += dfs(S ^ (1<<i), c+1)
    memo[S] = r = r %MOD
    return r
print(dfs((1<<N)-1,0))
### BUGGY CODE ###

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

### FIXED CODE ###

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

# seishin.py
N, M = map(int, input().split())
D = [[] for i in range(M+1)]
for i in range(N):
    l, r = map(int, input().split())
    D[r-l+1].append(l)

data = [0]*(M+2)
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def add(k, x):
    while k <= M+1:
        data[k] += x
        k += k & -k

C = N
ans = []
for d in range(1, M+1):
    for l in D[d]:
        add(l, 1)
        add(l+d, -1)
        C -= 1

    cnt = C
    i = d
    while i <= M:
        cnt += get(i)
        i += d
    ans.append(cnt)
print(*ans, sep='\n')


### FIXED CODE ###

# seishin.py
N, M = map(int, input().split())
D = [[] for i in range(M+1)]
for i in range(N):
    l, r = map(int, input().split())
    D[r-l+1].append(l)

data = [0]*(M+2)
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def add(k, x):
    while k <= M+1:
        data[k] += x
        k += k & -k

C = N
ans = []
for d in range(1, M+1):
    for l in D[d]:
        add(l, 1)
        add(l+d, -1)
        C -= 1

    cnt = C
    i = d
    while i <= M:
        cnt += get(i)
        i += d
    ans.append(cnt)
print(*ans, sep='\n')
### BUGGY CODE ###

n,m,x = map(int, input().split())
import numpy as np
C = []
A = np.array([[0]*m]*n)
for i in range(n):
    l = list(map(int, input().split()))
    C.append(l[0])
    A[i] += np.array(l[1:])
D = sum(A[j] for j in range(n))
ans=[sum(C)]
L=set(range(n))

def f(L, D, cost):
    global x, A
    for i in L:
        next_D = D-A[i]
        if min(next_D) >= x:
            ans.append(cost-C[i])
            next_L = L^{i}
            f(next_L, next_D, cost-C[i])
f(L, D, sum(C))

if min(D) < x:
    print(-1)
else:
    print(min(ans))

### FIXED CODE ###

n,m,x = map(int, input().split())
import numpy as np
C = np.array([0]*n)
A = np.array([[0]*m]*n)
for i in range(n):
    l = list(map(int, input().split()))
    C[i] += l[0]
    A[i] += np.array(l[1:])

def L(i):
    X = []
    for j in range(n):
        X.append(i%2)
        i = i//2
    X.reverse() 
    return np.array(X)

ans = []
for k in range(2**n):
    D = np.dot(L(k), A)
    if min(D) >= x:
        ans.append(np.dot(C, L(k)))
        
if ans == []:
    print(-1)
else:
    print(min(ans))
### BUGGY CODE ###

N = int(input())

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

A.sort()

ans = 0
for a in range(N-2):
    for b in range(a+1, N-1):
        for c in range(b+1, N):
            if A[c] < (A[a] + A[b]):
                ans += 1
            else:
                break

print(ans)

### FIXED CODE ###

import bisect

N = int(input())

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

A.sort()

ans = 0
for a in range(N-2):
    for b in range(a+1, N-1):
        ans += bisect.bisect_left(A, A[a]+A[b])-b-1

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

from math import floor
N,M = map(int,input().split())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def prime_decomposition(n):
  i = 2
  d = {2:0}
  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 = list(map(int,input().split()))
for i in range(N):
    A[i] //= 2

l = A[0]
for i in range(1,N):
    l = (l*A[i])//gcd(l,A[i])
ans = floor((M/l+1)/2)
n = prime_decomposition(l)[2]
p2 = 2**n
for i in range(N):
    if A[i]%p2 != 0:
        ans = 0
print(ans)

### FIXED CODE ###

from math import floor
from fractions import gcd
N,M = map(int,input().split())

def prime_decomposition(n):
  i = 2
  d = {2:0}
  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 = list(map(int,input().split()))
for i in range(N):
    A[i] //= 2

l = A[0]
for i in range(1,N):
    l = (l*A[i])//gcd(l,A[i])
    if l>M:
        break
ans = floor((M/l+1)/2)
n = prime_decomposition(l)[2]
p2 = 2**n
for i in range(N):
    if A[i]%p2 != 0:
        ans = 0
        break
print(ans)
### BUGGY CODE ###

a,b,n=map(int,input().split())
x=0
for i in range(n+1):
  if x<=((a*i)//b)-a*(i//b):
    x=((a*i)//b)-a*(i//b)
print(x)

### FIXED CODE ###

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

if n<b:
  print((a*n)//b)
else:
  print(a*(b-1)//b)
### BUGGY CODE ###

from copy import copy
def prime_table(n):
  n+=1
  table=[i if i%2 else 2 for i in range(n)]
  for i in range(3,n,2):
    if table[i]==i:
      for j in range(i*i,n,2*i):
        if table[j]==j:
          table[j]=i
  return table


def prime_fact(n,table):
  p=[]
  while n!=1:
    pp=table[n]
    p.append(pp)
    n//=pp
  r={}
  for i in p:
    if i in r:
      r[i]+=1
    else:
      r[i]=1
  return r



n=int(input())
t=prime_table(10**6)
a=list(map(lambda x:prime_fact(int(x),t),input().split()))
s={}
for i in a:
  for j in i:
    if j in s:
      s[j]+=i[j]
    else:
      s[j]=i[j]
b=[]
for i in a:
  b.append(copy(s))
  for j in i:
    b[-1][j]-=i[j]
    if b[-1][j]==0:
      del b[-1][j]
mn=copy(b[0])
for i in b[1:]:
  t=[]
  for j in mn:
    if j in i:
      mn[j]=min(mn[j],i[j])
    else:
      t.append(j)
  for j in t:
    del mn[j]

sm=0
mod=10**9+7
for i in a:
  r=1
  for j in i:
    r=(r*pow(j,i[j],mod))%mod
  sm=(sm+pow(r,mod-2,mod))%mod

  
p=1
for i in mn:
  p=(p*pow(i,mn[i],mod))%mod

q=1
for i in s:
  q=(q*pow(i,s[i],mod))%mod

print((q*sm*pow(p,mod-2,mod))%mod)

### FIXED CODE ###

from copy import copy
def prime_table(n):
  n+=1
  table=[i if i%2 else 2 for i in range(n)]
  for i in range(3,n,2):
    if table[i]==i:
      for j in range(i*i,n,2*i):
        if table[j]==j:
          table[j]=i
  return table


def prime_fact(n,table):
  p=[]
  while n!=1:
    pp=table[n]
    p.append(pp)
    n//=pp
  r={}
  for i in p:
    if i in r:
      r[i]+=1
    else:
      r[i]=1
  return r



n=int(input())
t=prime_table(10**6)
a=list(map(lambda x:prime_fact(int(x),t),input().split()))

mx=copy(a[0])
for i in a[1:]:
  for j in i:
    if j in mx:
      mx[j]=max(mx[j],i[j])
    else:
      mx[j]=i[j]


sm=0
mod=10**9+7
for i in a:
  r=1
  for j in i:
    r=(r*pow(j,i[j],mod))%mod
  sm=(sm+pow(r,mod-2,mod))%mod

  
p=1
for i in mx:
  p=(p*pow(i,mx[i],mod))%mod

print((sm*p)%mod)
### BUGGY CODE ###

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

cnt = 0

for X in range(min(A),max(A)+1):
    transient = 0
    for a in A:
        if -1 <= a -X <= 1:
            transient += 1
    else:
        if transient > cnt:
            cnt = transient

print(cnt)


### FIXED CODE ###

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

C = [0]*(10**5 + 2)

for i in A:
    C[i-1] += 1
    C[i] += 1
    C[i+1] += 1

print(max(C))
### BUGGY CODE ###

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

P = [[0 if x == "#" else 1 for x in input()]+[0] for _ in range(H)]
C = [[-1*P[x][y] for y in range(W)] + [0] for x in range(H)]
W += 1
H += 1
P.append([0] * W)
C.append([0] * W)


for i in range(H):
    cnt = 0
    for j in range(W):
        if P[i][j] == 0:
            for k in range(cnt):
                C[i][j-1-k] += k
            cnt = 0
        else:
            cnt += 1
        C[i][j] += cnt

for j in range(W):
    cnt = 0
    for i in range(H):
        if P[i][j] == 0:
            for k in range(cnt):
                C[i-1-k][j] += k
            cnt = 0
        else:
            cnt += 1
        C[i][j] += cnt


print(max((x for ci in C for x in ci)))


### FIXED CODE ###

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

P = [[0 if x == "#" else 1 for x in input()] for _ in range(H)]
C = [[-3*P[x][y] for y in range(W)] for x in range(H)]

for j in range(W):
    cntU = 0
    cntD = 0
    for i in range(H):
        if P[i][j] == 0:
            cntD = 0
        else:
            cntD += 1
        C[i][j] += cntD 

        if P[H-1-i][j] == 0:
            cntU = 0
        else:
            cntU += 1
        C[H-1-i][j] += cntU 

for i in range(H):
    cntR = 0
    cntL = 0
    for j in range(W):
        if P[i][j] == 0:
            cntR = 0
        else:
            cntR += 1
        C[i][j] += cntR 

        if P[i][W-1-j] == 0:
            cntL = 0
        else:
            cntL += 1
        C[i][W-1-j] += cntL 




print(max((x for ci in C for x in ci)))
### BUGGY CODE ###

import itertools as ito
N,K=map(int,input().split(" "))
X=list(map(int,input().split(" ")))

Ex=list(ito.permutations(X,K))

ans=0
for i in range(len(Ex)):
    tans=0
    tx=0
    for j in range(len(Ex[i])):
        tans+=abs(tx-Ex[i][j])
        tx=Ex[i][j]
        
    if tans<ans or i==0:
        ans=tans
    
print(ans)

### FIXED CODE ###

N,K=map(int,input().split(" "))
X=sorted(list(map(int,input().split(" "))))

ans=0
for i in range(N-K+1):
    tans=abs(X[i]-X[i+K-1])+abs(X[i])

    if i==0 or ans>tans:
        ans=tans

for i in range(N-K+1):
    tans=abs(X[i]-X[i+K-1])+abs(X[i+K-1])

    if ans>tans:
        ans=tans

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

input_lines = input().split()
N = int(input_lines[0])
M = int(input_lines[1])
S = input()
T = input()

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

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

L = int(lcm(N,M))
x = 1
count = 0
while True:
    k = L*x
    flag = 1
    for i in range(N):
        for j in range(M):
            hoge = (i-1)*k/N+1
            fuga = (j-1)*k/M+1
            if(hoge < fuga):
                break
            elif(hoge == fuga):
                if(S[i-1] != T[j-1]):
                    flag = 0
                    count += 1
                    break
        if(flag == 0):
            break
    if(flag == 1):
        print(k)
        break
    if(count == 2):
        print(-1)
        break
    x += 1


### FIXED CODE ###

input_lines = input().split()
N = int(input_lines[0])
M = int(input_lines[1])
S = input()
T = input()

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

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

L = int(lcm(N,M))
x = 1
count = 0
while True:
    k = L*x
    flag = 1
    starti = 0
    startj = 0
    for i in range(starti, N):
        for j in range(startj, M):
            hoge = i*k/N+1
            fuga = j*k/M+1
            if(hoge < fuga):
                startj = j - 1
                break
            elif(hoge == fuga):
                if(S[i] != T[j]):
                    flag = 0
                    count += 1
                    break
        if(flag == 0):
            break
    if(flag == 1):
        print(k)
        break
    if(count == 2):
        print(-1)
        break
    x += 1
### BUGGY CODE ###

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

d = {}

for i in range(N):
    d[i+1] = []

for i in range(M):
    a, b = map(int,input().split())
    d[a].append(b)
    d[b].append(a)

que = [1]
checked = set()
ans = {1:-1}

while que:
    now = que.pop(0)
    for h in d[now]:
        if not h in ans:
            ans[h] = now
            que.append(h)
    if len(ans) == N:
        break
    
if len(ans) == N:
    print('Yes')
    for i in range(N-1):
        print(ans[i+2]) 
else:
    print('No')



### FIXED CODE ###

from collections import deque

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

d = {}

for i in range(N):
    d[i+1] = set()

for i in range(M):
    a, b = map(int,input().split())
    d[a].add(b)
    d[b].add(a)

que = deque([1])
checked = set()
ans = {1:-1}

while que:
    now = que.popleft()
    for h in d[now]:
        if not h in ans:
            ans[h] = now
            que.append(h)
    if len(ans) == N:
        break
    
if len(ans) == N:
    print('Yes')
    for i in range(N-1):
        print(ans[i+2]) 
else:
    print('No')
### BUGGY CODE ###

# coding: utf-8
# Your code here!
n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
ans=0
for i in range(len(A)-1):
    for j in range(i+1,len(A)):
        ans+=A[i]*A[j]
        
print(ans%mod)

### FIXED CODE ###

# coding: utf-8
# Your code here!
n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
ans=0
s=[]
sum_a=0
for i in range(n-1):
    sum_a+=A[i]
    ans+=sum_a*A[i+1]
    #s.append(sum_a)
print(ans%mod)
"""
for i in range(len(A)-1):
    for j in range(i+1,len(A)):
        ans+=A[i]*A[j]
        
print(ans%mod)
"""
### BUGGY CODE ###

INF=10**20
from heapq import heappop,heappush,heapify
def dijkstra(G,H,W,sh,sw):
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    que=[(0,sh,sw)]
    dist=[[INF]*W for i in range(H)]
    dist[sh][sw]=0
    while que:
        mincost,h,w=heappop(que)
        if(mincost>dist[h][w]):
            continue
        for di in range(4):
            nh=h+dx[di]
            nw=w+dy[di]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(G[nh][nw]=='#'):
                continue
            if(dist[h][w]<dist[nh][nw]):
                dist[nh][nw]=dist[h][w]
                heappush(que,(dist[nh][nw],nh,nw))
        for nh in range(h-2,h+3):
            for nw in range(w-2,w+3):
                if (nh>H-1 or nh<0 or nw>W-1 or nw<0):
                    continue
                if(G[nh][nw]=='#'):
                    continue
                if dist[h][w]+1<dist[nh][nw]:
                    dist[nh][nw]=dist[h][w]+1
                    heappush(que,(dist[nh][nw],nh,nw))
    return dist

H,W=map(int,input().split())
Ch,Cw=map(lambda x:int(x)-1,input().split())
Dh,Dw=map(lambda x:int(x)-1,input().split())
G=[list(input()) for i in range(H)]
dist=dijkstra(G,H,W,Ch,Cw)
ans=dist[Dh][Dw]
if ans!=INF:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

INF=float('inf')
from collections import deque
def mbfs(G,sh,sw,H,W):
    dist=[[INF]*W for i in range(H)]
    dist[sh][sw]=0

    d=deque()
    d.append([sh,sw])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for dir in range(4):
            nh=h+dx[dir]
            nw=w+dy[dir]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(G[nh][nw]=='#'):
                continue
            if dist[nh][nw]>dist[h][w]:
                dist[nh][nw]=dist[h][w]
                d.appendleft([nh,nw])
        for i in range(h-2,h+3):
            for j in range(w-2,w+3):
                if (i>H-1 or i<0 or j>W-1 or j<0):
                    continue
                if (G[i][j]=='#'):
                    continue
                if dist[i][j]>dist[h][w]+1:
                    dist[i][j]=dist[h][w]+1
                    d.append([i,j])
    return dist

H,W=map(int,input().split())
Ch,Cw=map(lambda x:int(x)-1,input().split())
Dh,Dw=map(lambda x:int(x)-1,input().split())
G=[list(input()) for i in range(H)]

dist=mbfs(G,Ch,Cw,H,W)
if dist[Dh][Dw]!=INF:
    print(dist[Dh][Dw])
else:
    print(-1)
### BUGGY CODE ###

N=int(input())
lst=input().split()
for k in range(N):
    lst2=lst[:k]+lst[k+1:]
    count=0
    for i in lst2:
        for j in lst2:
            count+=i==j
    print((count-N+1)//2)

### FIXED CODE ###

import collections
N=int(input())
lst=input().split()
s=0
dic=collections.Counter(lst)
for i in dic.values():
    s+=(i*i-i)//2
for i in lst:
    print(s+1-dic[i])
### BUGGY CODE ###

L, R = map(int,input().rstrip().split())
ans = 2019
for i in range(L,R):
    for j in range(i+1,R+1):
        if (i*j)%2019<ans:
            ans=(i*j)%2019
print(ans)

### FIXED CODE ###

L, R = map(int,input().rstrip().split())
if R - L >=2018:
    ans = 0
else:
    ans = 2019
    for i in range(L,R):
        for j in range(i+1,R+1):
            if (i*j)%2019<ans:
                ans=(i*j)%2019
print(ans)
### BUGGY CODE ###

n = input()
sz = input().split(" ")
t = []
for i in range(len(sz)) :
    t.append(int(sz[i]))

ans = 0
mod = 1e9 + 7

for i in range(len(t)) :
    for j in range(i+1, len(t)) :
        ans += t[i]*t[j]

print(int(ans%mod))

### FIXED CODE ###

n = int(input())
sz = [int(x) for x in input().split(" ")]

ans = sum(sz)*sum(sz)

for i in sz :
    ans -= i*i

ans //= 2
ans %= (10**9+7)

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

h, w = map(int, input().split())
S = []
for _ in range(h):
    s = str(input())
    S.append(s)

# leftの個数カウントを行う
Left_count = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    s = S[i]
    count = 0
    for j in range(w):
        if s[j] == '#':
            count = 0
            continue
        else:
            count += 1
            Left_count[i][j] = count

# Rightの個数カウントを行う
Right_count = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    s = S[i][::-1]
    count = 0
    for j in range(w):
        if s[j] == '#':
            count = 0
            continue
        else:
            count += 1
            Right_count[i][j] = count
for i in range(h):
    Right_count[i] = Right_count[i][::-1]

# Upの個数カウントを行う
Up_count = [[0 for _ in range(w)] for _ in range(h)]
for j in range(w):
    count = 0
    for i in range(h):
        if S[i][j] == '#':
            count = 0
            continue
        else:
            count += 1
            Up_count[i][j] = count

# Downの個数カウントを行う
Down_count = [[0 for _ in range(w)] for _ in range(h)]
for j in range(w):
    count = 0
    for i in range(h-1,-1,-1):
        if S[i][j] == '#':
            count = 0
            continue
        else:
            count += 1
            Down_count[i][j] = count

ans = 0
for i in range(h):
    for j in range(w):
        tot_ij = Left_count[i][j] + Right_count[i][j] + Down_count[i][j] + Up_count[i][j] -3
        ans = max(tot_ij, ans)
print(ans)

### FIXED CODE ###

h, w = map(int, input().split())
S = []
for _ in range(h):
    s = str(input())
    S.append(s)

# leftの個数カウントを行う
Left_count = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    s = S[i]
    count = 0
    for j in range(w):
        if s[j] == '#':
            count = 0
            continue
        else:
            count += 1
            Left_count[i][j] = count

# Rightの個数カウントを行う
Right_count = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    s = S[i][::-1]
    count = 0
    for j in range(w):
        if s[j] == '#':
            count = 0
            continue
        else:
            count += 1
            Right_count[i][j] = count
for i in range(h):
    Right_count[i] = Right_count[i][::-1]

# Upの個数カウントを行う
Up_count = [[0 for _ in range(w)] for _ in range(h)]
for j in range(w):
    count = 0
    for i in range(h):
        if S[i][j] == '#':
            count = 0
            continue
        else:
            count += 1
            Up_count[i][j] = count

# Downの個数カウントを行う
Down_count = [[0 for _ in range(w)] for _ in range(h)]
for j in range(w):
    count = 0
    for i in range(h-1,-1,-1):
        if S[i][j] == '#':
            count = 0
            continue
        else:
            count += 1
            Down_count[i][j] = count

ans = 0
for i in range(h):
    for j in range(w):
        tot_ij = Left_count[i][j] + Right_count[i][j] + Down_count[i][j] + Up_count[i][j] -3
        ans = max(tot_ij, ans)
print(ans)
### BUGGY CODE ###

H,W,M = map(int, input().split())
mx=[0] * W
my=[0] * H
bs =[[] for i in range(H)]
mxx = 0
myy = 0
for i in range(M):
    y,x = map(int, input().split())
    mx[x-1] += 1
    my[y-1] += 1
    mxx = max(mx[x-1], mxx)
    myy = max(my[y-1], myy)
    bs[y-1].append(x-1)

vx = []
vy = []
for i,x in enumerate(mx):
    if x == mxx:
        vx.append(i)
for i,y in enumerate(my):
    if y == myy:
        vy.append(i)

a = 1
for i in vx:
    for j in vy:
        if i not in bs[j]:
            a = 0
            break
ans = mxx + myy - a
print(ans)


### FIXED CODE ###

H,W,M = map(int, input().split())
mx=[0] * W
my=[0] * H
bs ={}
mxx = 0
myy = 0
for i in range(M):
    y,x = map(int, input().split())
    mx[x-1] += 1
    my[y-1] += 1
    mxx = max(mx[x-1], mxx)
    myy = max(my[y-1], myy)
    if y-1 in bs:
        bs[y-1].add(x-1)
    else:
        bs[y-1] = set([x-1])

vx = []
vy = []
for i,x in enumerate(mx):
    if x == mxx:
        vx.append(i)
for i,y in enumerate(my):
    if y == myy:
        vy.append(i)

a = 1

for i in vx:
    for j in vy:
        if i not in bs[j]:
            a = 0
            break
    else:
        continue
    break

ans = mxx + myy - a
print(ans)
### BUGGY CODE ###

import collections
N, A, B = map(int, input().split())

cnt = []
for n in range(10 ** 100):
    if len(cnt) == N:
        break
    for i in range(A):
        if len(cnt) == N:
            break
        cnt.append("b")
    for j in range(B):
        if len(cnt) == N:
            break
        cnt.append("r")
ans = collections.Counter(cnt)
print(ans["b"])

### FIXED CODE ###

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

cnt = A * int(N / (A+B))
if (N % (A+B)) <= A:
    cnt += (N % (A+B))
else:
    cnt += A

print(cnt)
### BUGGY CODE ###

import heapq
INF = 10**18
n, m, p = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
for i in range(m):
    a, b, c = [int(item) for item in input().split()]
    a -= 1; b -= 1; c -= p
    c *= -1
    edge[a].append((b, c))

dist = [INF] * n
dist[0] = 0
update = 1
terminal_update = 0
for _ in range(n):
    update = 0
    for v, e in enumerate(edge):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
                if t == n-1:
                    terminal_update += 1
    if not update:
        print(max(0, -dist[n-1]))
        break
else:
    if terminal_update >= n:
        print(-1)
    else:
        print(max(0, -dist[n-1]))

### FIXED CODE ###

INF = 10**18
n, m, p = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
for i in range(m):
    a, b, c = [int(item) for item in input().split()]
    a -= 1; b -= 1; c -= p
    c *= -1
    edge[a].append((b, c))
 
dist = [INF] * n
dist[0] = 0
update = 1
terminal_update = 0
for _ in range(n * 2):
    update = 0
    for v, e in enumerate(edge):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
                if t == n-1:
                    terminal_update += 1
    if not update:
        print(max(0, -dist[n-1]))
        exit()
else:
    if terminal_update > 1:
        print(-1)
    else:
        print(max(0, -dist[n-1]))