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

import sys
import numpy as np
from scipy.sparse.csgraph import bellman_ford, connected_components
input = sys.stdin.readline


n, m, p = map(int, input().split())
l = np.zeros((n, n))
for i in range(m):
    a, b, c =map(int, input().split())
    c = p-c
    if c == 0:
        c = 10**(-7.9)
    if l[a-1][b-1] == 0:
        l[a-1][b-1] = c
    else:
        l[a-1][b-1] = min(l[a-1][b-1], c)
x = l[-1, 0]
l[-1][0] = 10**(-7.9)
n, labels = connected_components(l, connection="strong")
l = l[labels == labels[0]][:, labels == labels[0]]
l[-1, 0] = x
    
try:
    print(max(0, int(bellman_ford(l)[0][-1])*(-1)))
except:
    print(-1)



### FIXED CODE ###

import sys
import numpy as np
from scipy.sparse.csgraph import bellman_ford, connected_components
input = sys.stdin.readline


def main():
    n, m, p = map(int, input().split())
    
    l = np.zeros((n, n))
    for i in range(m):
        a, b, c =map(int, input().split())
        c = p-c
        if c == 0:
            c = 10**(-7.9)
        if l[a-1][b-1] == 0:
            l[a-1][b-1] = c
        else:
            l[a-1][b-1] = min(l[a-1][b-1], c)
    x = l[-1, 0]
    l[-1][0] = 10**(-7.9)
    n, labels = connected_components(l, connection="strong")
    l = l[labels == labels[0]][:, labels == labels[0]]
    l[-1, 0] = x
    
    try:
        print(max(0, int(round(bellman_ford(l, indices=0)[-1]))*(-1)))
    except:
        print(-1)


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

import bisect
s=input()
s=input().split()
t=input()
t=input().split()
for i in range(len(s)):
 s[i]=int(s[i])
for i in range(len(t)):
 t[i]=int(t[i])
s.sort()
t.sort()
f=False
for c in t:
 i=bisect.bisect_left(s,c)
 if s[i]!=c:
  print("NO")
  f=True
  break
 else:
  s.pop(i)
if not f:
 print("YES")

### FIXED CODE ###

lena=int(input())
s=input().split()
a=[]
for i in s:
 a.append(int(i))
a.sort()
lenb=int(input())
s=input().split()
b=[]
for i in s:
 b.append(int(i))
b.sort()
i=0
j=0
while i<lena:
    if a[i]==b[j]:
        i+=1
        j+=1
        if j==lenb:
            break
    elif a[i]<b[j]:
        i+=1
    else:
        break
if j==lenb:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

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

INF = 10 ** 9
dp = [INF] * (H+1)
dp[0] = 0
for i in range(H):
    for j in range(N):
        idx = min(H, i+ab[j][0])
        dp[idx] = min(dp[idx], dp[i]+ab[j][1])
print(dp[-1])

### FIXED CODE ###

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

INF = 10 ** 9
dp = [INF] * (H+1)
dp[0] = 0
for i in range(H):
    for j in range(N):
        idx = min(H, i+ab[j][0])
        dp[idx] = min(dp[idx], dp[i]+ab[j][1])
print(dp[-1])
### BUGGY CODE ###

s = input()
slist = list(s)
l = len(s)
n = 0
j = 1

while j > 0:
  j = 0
  for i in range(l-1):
    if slist[i:i+2] == ['B','W']:
      slist[i:i+2] = ['W','B']
      n += 1
      j += 1

print(n)

### FIXED CODE ###

S = input()
cnt = 0
ans = 0
left = 0
for i in range(len(S)):
    if S[i] == 'W':
        cnt += S[left:i].count('B')
        ans += cnt
        left = i
print(ans)
### BUGGY CODE ###

from collections import deque
A = deque()
A.append(list(input()))
while A[0] != [] and A[0] != [False]:
        if A[0][:7] == list("dreamer"):
            A.appendleft(A[0][7:])
            A[1] = A[1][5:]
        elif A[0][:5] == list("dream"):
            A[0] = A[0][5:]
        elif A[0][:6] == list("eraser"):
            A.appendleft(A[0][6:])
            A[1] = A[1][5:]
        elif A[0][:5] == list("erase"):
            A[0] = A[0][5:]
        else:
            A.popleft()
            if A == deque():
                A.append([False])
if A[0] == []:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

s = input().replace("eraser", "").replace("erase", "")
s = s.replace("dreamer", "").replace("dream", "")
if s:
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

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

relations = [[0 for j in range(N)] for i in range(N)]

tree = UnionFind(N)

for i in range(M):
    a, b = list(map(int, input().split()))
    relations[a-1][b-1] = 1
    relations[b-1][a-1] = 1
    tree.union(a-1, b-1)

for i in range(K):
    c, d = list(map(int, input().split()))
    relations[c-1][d-1] = 2
    relations[d-1][c-1] = 2

cnt = []

for i in range(N):
    cnt.append(0)
    for j in range(N):
        if i == j:
            continue
        if tree.same(i, j) and relations[i][j] == 0:
            cnt[-1] += 1

print(' '.join(list(map(str, cnt))))

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]

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

tree = UnionFind(N)
friends = [set() for i in range(N)]
blocks = [set() for i in range(N)]

for i in range(M):
    a, b = list(map(int, input().split()))
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)
    tree.union(a-1, b-1)

for i in range(K):
    c, d = list(map(int, input().split()))
    blocks[c-1].add(d-1)
    blocks[d-1].add(c-1)

cnt = []

for i in range(N):
    group_size = tree.size(i)
    friend_cnt = len(friends[i])
    block_cnt = len([j for j in blocks[i] if tree.same(i, j)])
    cnt.append(group_size - friend_cnt - block_cnt - 1)

print(' '.join(list(map(str, cnt))))
### BUGGY CODE ###

N = int(input())
S = [''] * N
for i in range(N) :
    S[i] = input()
S_set = list(set(S))

mmax = -1
word_buf = []
cnt = 0

for i in range(len(S_set)) :
    cnt = S.count(S_set[i])
    mmax = max(mmax,cnt)

for i in range(len(S_set)) :
    if S.count(S_set[i]) == mmax :
        word_buf.append(S_set[i])

word_buf = sorted(word_buf)
for i in range(len(word_buf)) :
    print(word_buf[i])

### FIXED CODE ###

from collections import Counter
N = int(input())
S = [''] * N
for i in range(N) :
    S[i] = input()
S = Counter(S).most_common()
c = S[0][1]

print(*sorted([a for a,s in S if s==c]),sep="\n")
### BUGGY CODE ###

N, Q = list(map(int, input().split()))
S = input()
target = "AC"

input_list = []
for i in range(Q):
    l, r = list(map(int, input().split()))
    print(S[l - 1 : r].count(target))


### FIXED CODE ###

from itertools import accumulate

N, Q = list(map(int, input().split()))
S = input()
target = "AC"

# ACが来たらカウントする
dp = [0] * N
for i in range(1, N):
    s = S[i - 1] + S[i]
    if s == "AC":
        dp[i] += 1

# 累積和
DP = list(accumulate(dp))

input_list = []
for i in range(Q):
    l, r = list(map(int, input().split()))
    print(DP[r - 1] - DP[l - 1])
### BUGGY CODE ###

import numpy as np

H,W = map(int,input().split())
# 周りに壁を、0,1化、壁を0で持つ
grid = np.zeros((H+2,W+2),dtype=object)
grid[1:-1,1:-1] = (np.array([list(input()) for _ in range(H)]) == '.')*1

f = np.frompyfunc(lambda x,y: x+1 if y else 0,2,1)

L = f.accumulate(grid,axis=1)
R = f.accumulate(grid[:,::-1],axis=1)[:,::-1]
U = f.accumulate(grid,axis=0)
D = f.accumulate(grid[::-1,:],axis=0)[::-1,:]

answer = (L+R+U+D).max()-3
print(answer)

### FIXED CODE ###

import numpy as np

H,W = map(int,input().split())
temp = np.array([list(input()) for _ in range(H)])
# 周りに壁を、0,1化
map = np.zeros((H+2,W+2),dtype=np.int32)
map[1:-1,1:-1][temp == '.'] = 1

# x軸正方向の集計
def F():
  x = map.copy()
  for row in range(1,H+1):
    zero_idx = np.nonzero(x[row]==0)[0]
    x[row, zero_idx[1:]] = 1-np.diff(zero_idx) # cumsumで求められるように変形
  x = x.cumsum(axis = 1)
  return x

# y軸
def G():
  x = map.T.copy()
  for row in range(1,W+1):
    zero_idx = np.nonzero(x[row]==0)[0]
    x[row, zero_idx[1:]] = 1-np.diff(zero_idx) # cumsumで求められるように変形
  x = x.cumsum(axis = 1)
  return x.T

answer = np.zeros_like(map)
# x軸
answer += F()
# 逆順
map = map[:,::-1]
answer += F()[:,::-1]
map = map[:,::-1]

# y軸
answer += G()
# 逆順
map = map[::-1,:]
answer += G()[::-1,:]

answer = np.max(answer) - 3
print(answer)
### BUGGY CODE ###



def main()->None:
    # a_iに１を足すか、１引くか、何もしないかの操作を行って、ある整数個数最大化をする
    # x を決めるとgreedyに決まる。
    # どうやってxを決めるのか。
    N = int(input())
    a = list(map(int, input().split()))
    range_N = range(N)
    max_counter = 0
    for i in range_N:
        X = a[i]
        tmp_count = 0
        for j in a:
            if j + 1 == X or j - 1 == X or j == X:
                tmp_count += 1

        if tmp_count > max_counter:
            max_counter = tmp_count

    print(max_counter)



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys


def main()->None:
    N = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    max_a = max(a)
    # print(max_a)
    l = [0 for _ in range(max_a+2)] # 配列の初期化、固定長、位置が配列の数字で要素がカウント
    for i in a:
        l[i] += 1
    res = 0
    for i in range(0, max_a+1):
        tmp = l[i-1]+l[i]+l[i+1]
        res = max(res, tmp)
    print(res)


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

n,m = map(int,input().split())
d = [[]]*(n+1)
q = [[]]*(n+1)
p = [0]*m
y = [0]*m
for i in range(m):
  p[i], y[i] = map(int,input().split())
  d[p[i]] = d[p[i]] + [y[i]]
for i in range(n+1):
  d[i] = sorted(d[i])
  d[i] = dict([[d[i][j],j] for j in range(len(d[i]))])
for i in range(m):
  print("{0:06d}".format(p[i])+"{0:06d}".format(d[p[i]][y[i]]+1))

### FIXED CODE ###

n,m = map(int,input().split())
d = dict()
p = [0]*m
y = [0]*m
c = [0]*m
a = []
for i in range(m):
  p[i], y[i] = map(int,input().split())
  a.append([y[i], i, p[i]])
a.sort()
for x in a:
  if x[2] in d:
    d[x[2]] =  d[x[2]] + 1
  else:
    d[x[2]] = 1
  c[x[1]] = d[x[2]]
for i in range(m):
  print("{0:06d}".format(p[i])+"{0:06d}".format(c[i]))
### BUGGY CODE ###

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

A = []
B = []
buff = [0 for i in range(M+1)]

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A.append(b)
        # buff[b] = 1
    if b == N:
        B.append(a)

# print(A)
# print(B)
for i in range(len(A)):
    for j in range(len(B)):
        if A[i] == B[j]:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')



### FIXED CODE ###

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

A = []
B = []
buff = [0 for i in range(N+1)]
buff2 = [0 for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A.append(b)
        # buff[b] = 1
        buff[b] = 1
    if b == N:
        B.append(a)
        buff2[a] = 1

for i in range(N+1):
    if buff[i] == 1 and buff2[i] == 1:
        print('POSSIBLE')
        exit()



# print(buff)
# print(buff2)

# seikai1 = []
# for i in range(N+1):
#     if buff[i] == 1:
#         seikai1.append(i)

# for i in range(N+1):
#     if buff2[i] == 1:
#         if i in seikai1:
#             print('POSSIBLE')
#             exit()
# for i in range(len(buff)):
#     for j in range(len(buff2)):
#         if buff[i] == 1 and buff2[j] == 1:
#             print('POSSIBLE')
#             exit()

print('IMPOSSIBLE')
### BUGGY CODE ###

N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    ans = 0
    for n in range(N):
        if S[n] % P == 0:
            ans += n + 1
    print(ans)
else:
    S = [(S[n] * 10**(N - n - 1)) % P for n in range(N)]
    T = [0]
    for n in range(N)[::-1]:
        T.append((T[-1] + S[n]) % P)
    lst = {i: 0 for i in range(P)}
    ans = 0
    for t in T:
        ans += lst[t]
        lst[t] += 1
    print(ans)


### FIXED CODE ###

N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    ans = 0
    for n in range(N):
        if S[n] % P == 0:
            ans += n + 1
    print(ans)
else:
    S = [(S[n] * pow(10, N - n - 1, P)) % P for n in range(N)]
    S.reverse()
    T = [0]
    for s in S:
        T.append((T[-1] + s) % P)
    lst = {i: 0 for i in range(P)}
    ans = 0
    for t in T:
        ans += lst[t]
        lst[t] += 1
    print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
num=[]
for i in range(n):
  num.append(s[:i].count('W')+s[i:].count('E'))
print(min(num))

### FIXED CODE ###

n=int(input())
s=input()
cnt=s.count('E') #西から0番目の人から見たときの向きを変える人数
m=cnt

#西からi番目の人がリーダーの時に向きを変える人の増減について
for i in range(n):
  if s[i]=='E':
    cnt-=1 
  else:
    cnt+=1
  m=min(m,cnt)
print(m)
### BUGGY CODE ###

n=int(input())
a=[int(input())  for i in range(n)]
b=list(a)
b.remove(max(a))
for i in range(n):
    if a[i] != max(a):
        print(max(a))
    else:
        print(max(b))


### FIXED CODE ###

n=int(input())
a=[int(input())  for i in range(n)]
b=list(a)
b.remove(max(a))
maxa=max(a)
maxb=max(b)
for i in range(n):
    if a[i] != maxa:
        print(maxa)
    else:
        print(maxb)
### BUGGY CODE ###

import hashlib
n = int(input())
A = [int(input()) for i in range(n)]
a = set(A)
ans = len(a)
for i in a:
    if A.count(i) % 2 == 0:
        ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
s = set()
for i in range(n):
    k = int(input())
    if k in s:
        s.remove(k)
    else:
        s.add(k)
print(len(s))
### BUGGY CODE ###

n,m,k=map(int,input().split())
a=[0]*(k+1)
a[0]=1
for i in range(1,k+1):
    a[i]=(a[i-1]*(n-i))//(i)
#print(a)
ans=0
mod=998244353
for i in range(k+1):
    ans+=((m%mod)*pow(m-1,n-i-1,mod)*(a[i]%mod))%mod
    ans%=mod
print(ans)

### FIXED CODE ###

import sys
 
mod = 998244353  # type: int
 
 
class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]  # 階乗を求めるためのキャッシュ
        self.invModulos = [0, 1]  # n^-1のキャッシュ
        self.invFactorial_ = [1, 1]  # (n^-1)!のキャッシュ
 
    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]
 
    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]
 
    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  # To make sure already calculated n^-1
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]
 
 
class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)
 
    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
 
 
def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m
n,m,k=map(int,input().split())
c=Combination(mod)
ans=0
for i in range(k+1):
    ans+=((powm(m-1,n-1-i,mod))*(c.ncr(n-1,i)%mod))%mod
    ans%=mod
m=m%mod
print((ans*m)%mod)
### BUGGY CODE ###

def li():
    return list(map(int, input().split()))
def mi():
    return map(int, input().split())
def ii():
    return int(input())
def lim(N):
    return [int(input()) for i in range(N)]

N = ii()
a = lim(N)

current = 1
visited = [1]
result = 1

while True:
    if a[current - 1] in visited:
        result = -1
        break
    elif a[current - 1] == 2:
        break
    visited.append(a[current - 1])
    current = a[current - 1]
    result += 1

print(result)

### FIXED CODE ###

def li():
    return list(map(int, input().split()))
def mi():
    return map(int, input().split())
def ii():
    return int(input())
def lim(N):
    return [int(input()) for i in range(N)]

N = ii()
a = lim(N)

current = 1
result = 1

for i in range(N):
    if a[current - 1] == 2:
        print(result)
        break
    else:
        current = a[current - 1]
        result += 1
else:
    print(-1)
### BUGGY CODE ###

n,p=map(int,input().split())
S=input()
M=[0]*p
M[0]=1
ans=0

if p==2 or p==5: #最下位だけで決まるとき
    for i in range(n):
        s=int(S[i])
        if s%p==0:
            ans+=i+1
    
else: #それ以外は末尾に0をつけても割り切れるかが一致する
    for i in range(n):
        s=int(S[(n-1-i):]) #右からi+1桁取り出す
        r=s%p #剰余
        if M[r]>=1: #同じ余りどうしで引き算すると割り切れる
            ans+=M[r]
        M[r]+=1

print(ans)

### FIXED CODE ###

n,p=map(int,input().split())
S=input()
M=[0]*p
M[0]=1
ans=0

if p==2 or p==5: #最下位だけで決まるとき
    for i in range(n):
        s=int(S[i])
        if s%p==0:
            ans+=i+1
    
else: #それ以外は末尾に0をつけても割り切れるかが一致する
    cnt=10%p #10の累乗の剰余を記録しておく
    for i in range(n):
        s=int(S[n-1-i]) #右からi+1桁目を取り出す
        if i==0:
            r=s%p #剰余
        else:
            r=(cnt*s+r)%p #前の剰余にs*cntをたす
            cnt=cnt*10%p #更新
        if M[r]>=1: #同じ余りどうしで引き算すると割り切れる
            ans+=M[r]
        M[r]+=1

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

import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
import random
D=N()
c=[0]+L()
s=[[0]*27]+[[0]+L() for i in range(D)]

dp=[]
T=[0]
ld=[0]*(27)
for i in range(1,D+1):
    ma=0
    t=0
    for j in range(1,27):
        tmp=s[i][j]+(i-ld[j])*(D-i+1)*c[j]
        if tmp>ma:
            ma=tmp
            t=j
    T.append(t)
    ld[t]=i

sc=sum(c)
def point():
    ld=[0]*(27)
    score=-sc*((D+1)*D//2)
    for i in range(1,D+1):
        t=T[i]
        score+=s[i][t]+(i-ld[t])*(D-i+1)*c[t]
        ld[t]=i
    return score

ma=point()
TT=T[:]
for i in range(30000):
    T=[random.randrange(1,27) for i in range(D+1)]
    tmp=point()
    if tmp>ma:
        ma=tmp
        TT=T[:]

        

T=TT[:]
now=point()
for i in range(300000):
    d1,q1=random.randrange(1,D+1),random.randrange(1,27)
    d2,q2=random.randrange(1,D+1),random.randrange(1,27)
    old1=T[d1]
    old2=T[d2]
    T[d1]=q1
    T[d2]=q2
    new=point()
    if new>now:
        now=new
    else:
        T[d1]=old1
        T[d2]=old2

for i in T[1:]:
    print(i)

### FIXED CODE ###


import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
def Yes(x):print("Yes")if x==True else print("No")

D=N()
c=[0]+L()
s=[[0]*27]+[[0]+L() for i in range(D)]

dp=[]
T=[0]
for i in range(1,D+1):
    ma=0
    t=0
    for j in range(1,27):
        if s[i][j]>ma:
            ma=s[i][j]
            t=j
    T.append(t)
        
sc=sum(c)
def point():
    ld=[0]*(27)
    score=-sc*((D+1)*D//2)
    for i in range(1,D+1):
        t=T[i]
        score+=s[i][t]+(i-ld[t])*(D-i+1)*c[t]
        ld[t]=i
    return score


now=point()
import random
for i in range(1000):
    d,q=random.randrange(1,D+1),random.randrange(1,27)
    old=T[d]
    T[d]=q
    new=point()
    if new>now:
        now=new
    else:
        T[d]=old
for i in T[1:]:
    print(i)
### BUGGY CODE ###

#C
L, R = list(map(int, input().split()))
result = 2018
for i in range(L,R+1):
    for s in range(i+1,R+1):
        a = 0
        b = 0
        a = i%2019
        b = s%2019
        x = (i*s)%2019
        if result >= x:
            result = x
print(result)

### FIXED CODE ###

#C
import sys
L, R = list(map(int, input().split()))
if (R - L) == 2019:
    result = 0
else:
    result = 2018
    for i in range(L,R+1):
        for s in range(i+1,R+1):
            x = (i*s)%2019
            if x == 0:
                result = 0
                print(0)
                sys.exit()
            elif result > x:
                result = x
print(result)
### BUGGY CODE ###

n = int(input())
h = list(map(int,input().split()))
h1 = [[h[i],i] for i in range(n)]
h1.sort()
a = list(map(int,input().split()))
dp = [0]*n
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    def max(self, i):
        # [0, i) の要素の最大値を返す
        s = 0
        i += 1
        while i>0:
            s = max(s,self.tree[i])
            i -= i & -i
        return s
 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] = max(x,self.tree[i])
            i += i & -i
bit = Bit(n+1)

for i in range(n):
    s = h1[i][1]
    x = a[s]+bit.max(s-1)
    dp[s] = x
    bit.add(s,x)
    
print(max(dp))

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
h1 = [[h[i],i] for i in range(n)]
h1.sort()
a = list(map(int,input().split()))
dp = [0]*n
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    def max(self, i):
        # [0, i) の要素の最大値を返す
        s = 0
        i += 1
        while i>0:
            s = max(s,self.tree[i])
            i -= i & -i
        return s
 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] = max(x,self.tree[i])
            i += i & -i
bit = Bit(2*n+1)

for i in range(n):
    s = h1[i][1]
    x = a[s]+bit.max(s-1)
    dp[s] = x
    bit.add(s,x)
    
print(max(dp))
### BUGGY CODE ###

n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0
for a in range(n-2):
    for b in range(a+1, n-1):
        for c in range(b+1, n):
            if l[a]<l[b]+l[c] and l[b]<l[c]+l[a] and l[c]<l[a]+l[b]: ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
from bisect import bisect_left
for i in range(n-2):
  for j in range(i+1, n-1):
    ab = l[i] + l[j]
    idx = bisect_left(l, ab)
    ans += max(idx-j-1, 0)
print(ans)