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

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

### FIXED CODE ###

lr = input().split()
l = int(lr[0])
r = int(lr[1])
 
mini = 2018
 
for i in range(l, r+1):
  for j in range(i+1, r+1):
    mini = min(mini, (i*j)%2019)
 
    if mini==0:
      break
  if mini==0:
    break
print(mini)
### BUGGY CODE ###

import collections
n = int(input())
s = [0] * n
c = [0] * n
count = 0
for i in range(n):
    s[i] = input()
    c[i] = collections.Counter(s[i])
for i in range(n):
    for j in range(i+1,n):
        if c[i] == c[j]:
            count += 1
print(count)

### FIXED CODE ###

import collections
n = int(input())
s = [0] * n
c = [0] * n

count = 0
for i in range(n):
    s[i] = input()
    c[i] = ''.join(sorted(s[i]))
for i in collections.Counter(c).values():
    count += i*(i-1)//2
print(count)
### BUGGY CODE ###

N=int(input())

for h in range(1,3501):
  for n in range(1,3501):
    if (4*h*n-N*n-N*h) and (4*h*n-N*n-N*h) > 0 and (N*h*n) % (4*h*n-N*n-N*h)==0:
      print(h,n,(N*h*n) // (4*h*n-N*n-N*h))
      exit()

### FIXED CODE ###

N=int(input())

for h in range(1,3501):
  for n in range(1,3501):
    if (4*h*n-N*n-N*h) and (4*h*n-N*n-N*h) > 0 and (N*h*n) % (4*h*n-N*n-N*h)==0:
      print(h,n,(N*h*n) // (4*h*n-N*n-N*h))
      exit()
### BUGGY CODE ###

import itertools


X, Y, Z, K  = map(int, input().split())

A = sorted(list(map(int, input().split())), reverse=True)[:K]
B = sorted(list(map(int, input().split())), reverse=True)[:K]
C = sorted(list(map(int, input().split())), reverse=True)[:K]

AB  = sorted([sum(ab)  for ab  in itertools.product(A,  B)], reverse=True)[:K]
ABC = sorted([sum(abc) for abc in itertools.product(AB, C)], reverse=True)[:K]

for abc in ABC:
    print(abc)


### FIXED CODE ###

X, Y, Z, K  = map(int, input().split())

A = sorted(list(map(int, input().split())), reverse=True)[:K]
B = sorted(list(map(int, input().split())), reverse=True)[:K]
C = sorted(list(map(int, input().split())), reverse=True)[:K]

R  = [sum([A[0], B[0], C[0]])]
Q  = {(0, 0, 1), (0, 1, 0), (1, 0, 0)}
D  = {(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0)}
iS = [((a, b, c), sum([A[a], B[b], C[c]])) for a, b, c in Q if (a < X) and (b < Y) and (c < Z)]
iS = sorted(iS, key=lambda x: [x[1], x[0]], reverse=True)

while len(R) < K:
    R.append(iS[0][1])
    abc     = iS[0][0]
    a, b, c = abc[0], abc[1], abc[2]
    iS      = iS[1:]
    if a + 1 < X:
        if not (a + 1, b, c) in D:
            s = sum([A[a + 1], B[b], C[c]])
            is_done = False
            for i in range(len(iS)):
                if iS[i][1] < s:
                    iS = iS[:i] + [((a + 1, b, c), s)] + iS[i:]
                    is_done = True
                    break
            if is_done == False:
                iS = iS + [((a + 1, b, c), s)]
            D.add((a + 1, b, c))
    if b + 1 < Y:
        if not (a, b + 1, c) in D:
            s = sum([A[a], B[b + 1], C[c]])
            is_done = False
            for i in range(len(iS)):
                if iS[i][1] < s:
                    iS = iS[:i] + [((a, b + 1, c), s)] + iS[i:]
                    is_done = True
                    break
            if is_done == False:
                iS = iS + [((a, b + 1, c), s)]
            D.add((a, b + 1, c))
    if c + 1 < Z:
        if not (a, b, c + 1) in D:
            s = sum([A[a], B[b], C[c + 1]])
            is_done = False
            for i in range(len(iS)):
                if iS[i][1] < s:
                    iS = iS[:i] + [((a, b, c + 1), s)] + iS[i:]
                    is_done = True
                    break
            if is_done == False:
                iS = iS + [((a, b, c + 1), s)]
            D.add((a, b, c + 1))

for r in R:
    print(r)
### BUGGY CODE ###

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

if N > K:
    x = N-K
else:
    x = K-N

while  N > x :
    N = x

    if N > K:
        x = N-K

    else:
        x = K-N

print(N)

### FIXED CODE ###

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

if N > K:
    x = N%K
else:
    x = K-N

while  N > x :
    N = x

    if N > K:
        x = N-K

    else:
        x = K-N

print(N)
### BUGGY CODE ###

from collections import Counter

s=input()[::-1]
ans=0
lst=[]
num=0
for j in range(len(s)):
    
    lst.append(num%2019)
    num+=int(s[j])*10**(j)
lst.append(num%2019)

cou=dict(Counter(lst))
for x in cou.values():
    ans+=x*(x-1)/2
print(int(ans))

### FIXED CODE ###

from collections import Counter

s=input()[::-1]
ans=0
lst=[0]
num=0
p=1
for i in s:
    lst.append((int(i)*p+lst[-1])%2019)
    p=p*10%2019

ans=sum(x*(x-1)//2 for x in Counter(lst).values())
print(ans)
### BUGGY CODE ###

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

edges = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    edges[u-1].append(v-1)

S, T = map(int, sys.stdin.readline().split())
S -= 1
T -= 1

visited = {}
q = deque()
q.append((S, 0))
d = -1
while q:
    s, c = q.popleft()
    if s in visited and visited[s] % 3 == c % 3:
        continue
    visited[s] = c
    for n in edges[s]:
        if n == T and c % 3 == 2:
            d = c + 1
            break
        q.append((n, c+1))

    if d % 3 == 0:
        break

if d == -1:
    print(-1)
else:
    print(d // 3)

### FIXED CODE ###

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

edges = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    edges[u-1].append(v-1)

S, T = map(int, sys.stdin.readline().split())
S -= 1
T -= 1

visited = {}
q = deque()
q.append((S, 0))
d = -1
while q:
    s, c = q.popleft()
    if s in visited and (c % 3) in visited[s]:
        continue
    if s not in visited:
        visited[s] = set()
    visited[s].add(c % 3)
    for n in edges[s]:
        if n == T and c % 3 == 2:
            d = c + 1
            break
        q.append((n, c+1))

    if d % 3 == 0:
        break

if d == -1:
    print(-1)
else:
    print(d // 3)
### BUGGY CODE ###

N = int(input())

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

ans = 0

for i in range(N):
  if i == 0:
    ans += 1
    continue
    
  true = 1
  for j in range(i):
    if P[i] > P[j]:
      true = 0
      break
  
  if true == 1:
    ans += 1

print(ans)

### FIXED CODE ###

N = int(input())

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

ans = 1
minj = 0

for i in range(1, N):
  
  if P[i] < P[minj]:
    ans += 1
    minj = i

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

h,w = map(int,input().split())
la = [list(map(int,input().split())) for i in range(h)]
lb = [list(map(int,input().split())) for i in range(h)]
k = (h+w)*80+2

dp = [[[-1 for l in range(k)] for i in range(w)] for j in range(h)]

dp[0][0][abs(la[0][0]-lb[0][0])] = 1


for i in range(h):
    for j in range(w):
        for l in range(k):
            if dp[i][j][l] == 1:
                if j + 1 < w:
                    a = abs(la[i][j+1]-lb[i][j+1])
                
                    dp[i][j+1][l+a] = 1
                    dp[i][j+1][abs(l-a)] = 1
                if i + 1 < h:
                    a = abs(la[i+1][j]-lb[i+1][j])
                
                    dp[i+1][j][l+a] = 1
                    dp[i+1][j][abs(l-a)] = 1
for i in range(k):
    if dp[-1][-1][i] == 1:
        print(i)
        exit()

### FIXED CODE ###

import sys
input = sys.stdin.readline
h,w = map(int,input().split())
la = [list(map(int,input().split())) for i in range(h)]
for i in range(h):
    l = list(map(int,input().split()))
    for j,num in enumerate(l):
        la[i][j] = abs(la[i][j]-num)
dp = [[0 for i in range(w)] for j in range(h)]
k = (h+w)*80+2
dp[0][0] = 1 << (k+la[0][0]) | 1 << (k-la[0][0])

for i in range(h):
    for j in range(w):
        if i:
            dp[i][j] |= (dp[i-1][j] << la[i][j]) | dp[i-1][j] >> la[i][j]
        if j:
            dp[i][j] |= (dp[i][j-1] << la[i][j]) | dp[i][j-1] >> la[i][j]
        
s = bin(dp[-1][-1])[2:]
l = len(s)-1
ans = float('inf')
for i in range(l,-1,-1):
  if s[i]=='1':
    m = abs(l-i-k)
    if m<ans:
      ans = m
print(ans)
### BUGGY CODE ###

n=int(input())
k=1
ans=0
for i in range (n):
    k=k*(i+1)
for j in range(k):
    if k%(j+1)==0:
        ans+=1
print(ans%1000000007)


### FIXED CODE ###

n=int(input())
l=[k for k in range(1,n+1)]
phrase=[]
ans=1
a=1
def prime(x):
    i=2
    while i*i<=x:
        if x%i==0:
            return False
        i+=1
    return True
for i in range(2,n+1):
    if prime(i):
        phrase.append(i)
for j in phrase:
    for m in range(n):
        while l[m]%j==0:
            a+=1
            l[m]=l[m]/j
    ans=ans*a
    a=1
print(ans%1000000007)
### BUGGY CODE ###

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

L.sort()
count = 0

for i in reversed(range(N)):
  for j in reversed(range(i)):
    for k in range(j):
      if L[j] + L[k] > L[i]:
        count += j - k
        break
        
print(count)

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
 
L.sort()
count = 0
 
for i in reversed(range(N)):
  kmin = 0
  for j in reversed(range(i)):
    for k in range(kmin,j):
      if L[j] + L[k] > L[i]:
        count += j - k
        kmin = k
        break
        
print(count)
### BUGGY CODE ###

n = int(input())
pp = list(map(float,input().split()))

dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] =1

for i in range(n):
  for j in range(n):
    dp[i+1][j+1] += dp[i][j] * pp[i]
    dp[i+1][j] += dp[i][j] * (1-pp[i])
    
print(sum(dp[-1][(n+1)//2:]))

### FIXED CODE ###

n = int(input())
pp = list(map(float,input().split()))

dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] =1

for i in range(n):
  for j in range(n):
    dp[i+1][j+1] += dp[i][j] * pp[i]
    dp[i+1][j] += dp[i][j] * (1-pp[i])
    
print(sum(dp[-1][(n+1)//2:]))
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
last = [n]*n
for i in range(k):
    temp = [0]*n
    for j in range(n):
        b = a[j]
        temp[j] += 1
        for k in range(1, b + 1):
            if j + k < n:
                temp[j + k] += 1
            if j - k >= 0:
                temp[j - k] += 1
    a = temp[:]
    if a == last:
        print(*a)
        sys.exit()
print(*a)


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
from itertools import accumulate
for i in range(k):
    temp = [0]*(n + 1)
    for j in range(n):
        b = a[j]
        left = max(0, j - b)
        right = min(n - 1, j + b)
        temp[left] += 1
        temp[right + 1] -= 1
    a = list(accumulate(temp))[:n]
    if min(a) == n:
        print(*a)
        sys.exit()
print(*a)
### BUGGY CODE ###

import math

def divs(k):
    i=1
    cnt = 0
    hei = 0

    while i <= k**.5:
        if (k**.5).is_integer():
            hei = 1
        if k%i==0:
            cnt+=1
        i+=1
    if hei == 1:
        return cnt*2-1
    return cnt*2

n = int(input())
count = 0
for i in range(1,n,1):
    k = n-i
    count += divs(k)
print(count)


### FIXED CODE ###

n = int(input())
sum = 0
for i in range(1,n):
    sum+=(n-1)//i
print(sum)
### BUGGY CODE ###

def main():
    from fractions import gcd
    import sys
    n=int(input())
    a = tuple(map(int, input().split()))
    ans = a[0]

    #mmm=10**9+7
    for i in a[1:]:
        ans = ans *i // gcd(ans, i)

    result=0
    for item in a:
      result=(result+ans//item)

    print(result%(10**9+7))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from fractions import gcd
    import sys
    n=int(input())
    a = tuple(map(int, input().split()))
    ans = 1

    mmm=10**9+7
    for i in a:
        ans = ans *i // gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

    print(result%mmm)

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

#!/usr/bin/env python3
import sys
from collections import deque

def solve(N, M, to, start, goal):
    def kenkenpa(f):
        t = []
        for k1 in to[f]:
            for k2 in to[k1]:
                for pa in to[k2]:
                    t.append(pa)
        return t

    new_to = [ [] for _ in range(N+1) ]
    for i in range(1, N+1):
        new_to[i] = kenkenpa(i)
    
    costs = [float('inf')] * (N+1)
    costs[start] = 0

    q = deque()
    q.append(start)

    while len(q) != 0:
        u = q.popleft()
        if u == goal: return costs[u]
        for v in new_to[u]:
            if costs[u] + 1 < costs[v]:
                costs[v] = costs[u] + 1
                q.append(v)
    return -1



def main():
    N, M = map(int, input().split())
    to = [ [] for _ in range(N+1) ]
    for _ in range(M):
        u, v = map(int, input().split())
        to[u].append(v)
    S, T = map(int, input().split())
    print(solve(N, M, to, S, T))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

def solve(N, M, to, start, goal):
    costs = [float('inf')] * (3*N+3)
    costs[start] = 0

    q = deque([start])

    while len(q) != 0:
        u = q.popleft()
        for v in to[u]:
            if costs[u] + 1 < costs[v]:
                costs[v] = costs[u] + 1
                if v == goal: return costs[v] // 3
                q.append(v)
    return -1



def main():
    N, M = map(int, input().split())
    to = [ [] for _ in range(3*N+3) ]
    for _ in range(M):
        u, v = map(int, input().split())
        for i in range(3):
            to[u + (N+1)*i].append(v + (N+1) * ((i+1)%3))
    S, T = map(int, input().split())
    print(solve(N, M, to, S, T))

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

def yakusu(n):
    results = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            results.append(i)
            results.append(n // i)
    return results

N = int(input())
A = list(map(int, input().split()))
is_odd = [False for i in range(N+1)]
A.insert(0, 0)
ans = []
for i in range(N, 0, -1):
    if A[i] == 1:
        if not is_odd[i]:
            ans.append(i)
            for y in set(yakusu(i)):
                is_odd[y] = not is_odd[y]
    elif A[i] == 0:
        if is_odd[i]:
            ans.append(i)
            for y in set(yakusu(i)):
                is_odd[y] = not is_odd[y]
print(len(ans))
if len(ans) != 0:
    print(' '.join(map(str, ans)))


### FIXED CODE ###

def yakusu(n):
    results = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            results.append(i)
            results.append(n // i)
    return results

N = int(input())
A = list(map(int, input().split()))
is_odd = [False for i in range(N+1)]
A.insert(0, 0)
ans = []
for i in range(N, 0, -1):
    if A[i] == 1:
        if not is_odd[i]:
            ans.append(i)
            for y in set(yakusu(i)):
                is_odd[y] = not is_odd[y]
    elif A[i] == 0:
        if is_odd[i]:
            ans.append(i)
            for y in set(yakusu(i)):
                is_odd[y] = not is_odd[y]
print(len(ans))
if len(ans) != 0:
    print(' '.join(map(str, ans)))
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(n):
    yakusuu = 0
    k = int(input())
    for j in range(1, k+1):
        if k % j == 0:
            yakusuu += 1
        if yakusuu > 2:
            break
    if yakusuu == 2:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(n):
    k = int(input())
    j = 2
    flag = 0
    while k/j >= j:
        if k % j == 0:
            flag = 1
            break
        j += 1
    if flag == 0:
        ans += 1
print(ans)
### BUGGY CODE ###

l = 0
cnt = 0
def sum_lr(r):
    global l
    global cnt
    cnt += 1
    lr = l + r
    if lr < 10:
        l = lr
    else:
        l = lr // 10
        r = lr % 10
        sum_lr(r)


M = int(input())

nums = []
for _ in range(M):
    d, c = map(int, input().split())
    nums.append((d,c))
    
for d, c in nums:
    for _ in range(c):
        sum_lr(d)

print(cnt-1)

### FIXED CODE ###

def sum_lr(l, r, cnt):
    cnt += 1
    lr = l + r
    if lr < 10:
        l = lr
        return l, cnt
    else:
        l = lr // 10
        r = lr % 10
        return sum_lr(l, r, cnt)

from collections import defaultdict
aaa = defaultdict(lambda:{})
for l in range(10):
    for r in range(10):
        aaa[l][r] = sum_lr(l,r,0)
        

def dc_compression(d, c, ret, cnt):
    if c == 1:
        ret.append((d, 1))
        return ret, cnt
    
    if c % 2 == 1:
        ret.append((d, 1))
        c -= 1
    d, tmp_cnt = aaa[d][d]
    c = c // 2
    cnt += tmp_cnt * c
    #print(d, c, ret, cnt)
    return dc_compression(d, c, ret, cnt)
    
    
    
        

M = int(input())

nums = []
l = 0
cnt = 0
import sys
input = sys.stdin.readline
for _ in range(M):
    d, c = map(int, input().split())
    tmp_nums, tmp_cnt= dc_compression(d,c,[], 0)
    for t,_ in tmp_nums:
        nums.append(t)
    
    cnt += tmp_cnt
    
#print(nums)    
    
for d in nums:
    l, tmp_cnt = aaa[l][d]
    cnt += tmp_cnt

print(cnt-1)
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()

    password = set()

    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            for k in range(j + 1, N):
                candidate = S[i] + S[j] + S[k]
                password.add(candidate)

    print(len(password))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    ans = 0
    # password = set()

    # for i in range(N - 2):
    #     for j in range(i + 1, N - 1):
    #         for k in range(10):
    #             if str(k) in S[j + 1:]:
    #                 password.add(S[i] + S[j] + str(k))

    for i in range(10):
        for j in range(10):
            for k in range(10):
                i_index = S.find(str(i))
                j_index = S.find(str(j), i_index + 1)
                k_index = S.find(str(k), j_index + 1)
                if i_index != -1 and j_index != -1 and k_index != -1:
                    ans += 1

    print(ans)


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

import sys

def encode(s):
    alp = [0]*26
    for c in s:
        alp[ord(c)-97] += 1
    return tuple(alp)

def main():
    N = int(sys.stdin.readline())
    S = [encode(x.rstrip()) for x in sys.stdin.readlines()]

    dic = {}
    for i, s in enumerate(S):
        if s not in dic:
            dic[s] = [i]
        else:
            dic[s].append(i)

    count = 0
    for i, s in enumerate(S):
        count += len([x for x in dic[s] if x > i])

    print(count)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys

def main():
    N = int(sys.stdin.readline())
    S = [tuple(sorted(x.rstrip())) for x in sys.stdin.readlines()]

    dic = {}
    for i, s in enumerate(S):
        if s not in dic:
            dic[s] = {i:1}
        else:
            dic[s][i] = len(dic[s])+1

    count = 0
    for i, s in enumerate(S):
        count += len(dic[s]) - dic[s][i]

    print(count)

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

import sys
input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
v1 = x1*(w+1)+y1
v2 = x2*(w+1)+y2
C = list("".join(input().rstrip()+"@" for _ in range(h)))
ans = 0
stack = [v1]
next_vs = set()
while stack:
  for v in stack:
    if v == v2:
      print(ans)
      exit()
    for dr in (-(w+1), -1, 1, w+1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1) and C[nv] == ".":
          next_vs.add(nv)
        else:
          break
  for v in stack:
    C[v] = "@"
  stack = list(next_vs)
  next_vs = set()
  ans += 1
else:
  print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = "".join(input().rstrip()+"@" for _ in range(h))
  dist = [-1 if c=="@" else 10**10 for c in C]
  ans = 0
  que = deque()
  que.append(v1)
  dist[v1] = 0
  while que:
    v = que.popleft()
    if v == v2:
      print(dist[v2])
      exit()
    d = dist[v]+1
    for dr in (-(w+1), -1, w+1, 1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1):
          if dist[nv] > d:
            dist[nv] = d
            que.append(nv)
          elif dist[nv] == d:
            continue
          else:
            break
        else:
          break
  print(-1)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

R,C,K=map(int,input().split())
Item=[["*"]*(C+1)]+[["*"]+[0]*C for _ in range(R)]
T=3

for _ in range(K):
    y,x,v=map(int,input().split())
    Item[y][x]=v

DP=[[[0]*(T+1) for _ in range(C+1)] for _ in range(R+1)]

for y in range(1,R+1):
    for x in range(1,C+1):
        #右に移動
        for k in range(1,T+1):
            DP[y][x][k]=max(DP[y][x][k],DP[y][x-1][k],DP[y][x-1][k-1]+Item[y][x])

        #下に移動
        if y<R:
            for k in range(T+1):
                DP[y+1][x][0]=DP[y][x][-1]
                DP[y+1][x][1]=DP[y+1][x][2]=DP[y+1][x][3]=DP[y+1][x][0]+Item[y+1][x]

print(max(DP[-1][-1]))

### FIXED CODE ###

R,C,K=map(int,input().split())

Value=[[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r,c,v=map(int,input().split())
    Value[r][c]=v

DP=[[0,0,0,0] for _ in range(C+1) ]

for y in range(1,R+1):
    #下に移動
    for x in range(1,C+1):
        DP[x][0]=max(DP[x])
        DP[x][1]=DP[x][0]+Value[y][x]
        DP[x][2]=DP[x][3]=0

    #右に移動
    for x in range(1,C+1):
        for k in range(0,3+1):
            DP[x][k]=max(DP[x][k],DP[x-1][k])

        for k in range(1,3+1):
            DP[x][k]=max(DP[x][k],DP[x-1][k-1]+Value[y][x])

print(max(DP[-1]))
### BUGGY CODE ###

N = int(input())
S = input()

ans = 0
for i in range(1, N):
    S1 = S[:i]
    S2 = S[i:]
    ok = 0
    ng = len(S2) + 1
    k = (ok + ng) // 2
    while ng - ok > 1:
        if S2[:k] in S1:
            ok = k
            k = (k + ng) // 2
        else:
            ng = k
            k = (k + ok) // 2
    ans = max(ans, k)
print(ans)


### FIXED CODE ###

from collections import defaultdict

N = int(input())
S = input()
mod1 = 10 ** 9 + 7
mod2 = 10 ** 9 + 9
base1 = 1007
base2 = 2009

ok = 0
ng = N // 2 + 1
mid = (ok + ng) // 2
while ng - ok > 1:
    seen1 = defaultdict(lambda: 10 ** 5)
    seen2 = defaultdict(lambda: 10 ** 5)
    rh1 = 0
    rh2 = 0
    for i in range(mid):
        rh1 += ord(S[i]) * pow(base1, mid - i - 1, mod1)
        rh2 += ord(S[i]) * pow(base2, mid - i - 1, mod2)
        rh1 %= mod1
        rh2 %= mod2
    seen1[rh1] = 0
    seen2[rh2] = 0
    flag = 0
    for i in range(1, N - mid + 1):
        if flag == 1:
            break
        rh1 = (rh1 * base1 + ord(S[i + mid - 1]) - ord(S[i - 1]) * pow(base1, mid, mod1)) % mod1
        rh2 = (rh2 * base2 + ord(S[i + mid - 1]) - ord(S[i - 1]) * pow(base2, mid, mod2)) % mod2
        if i - seen1[rh1] >= mid and i - seen2[rh2] >= mid:
            ok = mid
            mid = (ok + ng) // 2
            flag = 1
        else:
            if seen1[rh1] == 10 ** 5:
                seen1[rh1] = i
            if seen2[rh2] == 10 ** 5:
                seen2[rh2] = i
    if flag == 0:
        ng = mid
        mid = (ok + ng) // 2

print(ok)
### BUGGY CODE ###

# M日後に最大の値
from heapq import heappush, heappop
N, M = map(int, input().split())
# [0] -> 日数, [1] -> お金
Data = [list(map(int, input().split())) for _ in range(N)]

heap = []
ans = 0
for i in range(1, M+1):
    N = len(Data)

    for j in range(N-1, -1, -1):  #range(N)
        if (Data[j][0] <= i):
            iranai = Data.pop(j)
            heappush(heap, -(iranai[1]))

    if len(heap) != 0:
        ans += -(heappop(heap))

print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
N, M = map(int, input().split())

Data = [list(map(int, input().split())) for _ in range(N)]
Data.sort(reverse = True)

heap = [0] * M
ans = 0
for i in range(1, M+1):
    N = len(Data)
    for j in range(N-1, -1, -1):
        if Data[j][0] > i:
            break
        if (Data[j][0] <= i):
            heappush(heap, -(Data.pop(j)[1]))

    ans += -(heappop(heap))

print(ans)