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

#!/usr/bin/env python3
import sys


def solve(N: int):
    for i in range(1, 3501):
        for j in range(i, 3501):
            z = 4*i*j - N*(j+i)
            if z != 0:
                h, r = divmod((N*i*j), z)
                if r == 0 and 0 <= h:
                    print(h, i, j)
                    exit()
            

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


# #!/usr/bin/env python3
# n = int(input())
# for i in range(1, 3501):
#   for j in range(1, 3501):
#     seed = 4 * i * j - n * (i + j) 
#     if seed > 0:
#       k, mod = divmod(n * i * j, seed) 
#       if mod == 0:
#         print(i, j, k)
#         exit()

### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int):
    for i in range(1, 3501):
        for j in range(i, 3501):
            z = 4*i*j - N*(j+i)
            if z > 0:
                h, r = divmod((N*i*j), z)
                if r == 0:
                    print(h, i, j)
                    exit()
            

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


# #!/usr/bin/env python3
# n = int(input())
# for i in range(1, 3501):
#   for j in range(1, 3501):
#     seed = 4 * i * j - n * (i + j) 
#     if seed > 0:
#       k, mod = divmod(n * i * j, seed) 
#       if mod == 0:
#         print(i, j, k)
#         exit()
### BUGGY CODE ###

n = int(input())
listx = [int(input()) for i in range(n)]
listx.sort()
listy=[]
ans=0

x=listx.pop(0)
listy.append(x)
x=listx.pop(-1)
listy.append(x)
ans+=int(listy[1])-int(listy[0])

while len(listx)>=1:
    abs1=abs(listx[0]-listy[-1])
    abs2=abs(listx[-1]-listy[0])

    if abs1 < abs2:
        x=listx.pop(-1)
        listy.insert(0,x)
        ans+=abs2
    else:
        x=listx.pop(0)
        listy.append(x)
        ans+=abs1
    
    if listy[0] > listy[-1]:
        listy.reverse()

print(ans)


### FIXED CODE ###

import itertools
import numpy as np
data_num = int(input()) 
data = [int(input()) for i in range(data_num)] 
#data_num=5
#data=[6,8,1,2,3]

data.sort()
npdata=np.array(data)

parts1=[1]
parts2=[2 for i in range(data_num-2)]
parts1.extend(parts2)
parts1.append(1)
npparts1=np.array(parts1)

parts0=[(-1)**(i+1) for i in range(data_num)]
npparts0=np.array(parts0)

y=npparts1*npparts0

y=y.tolist()
y.sort()

y=np.array(y)
z1=sum(data*y)

parts01=[(-1)**i for i in range(data_num)]
npparts0=np.array(parts01)

y=npparts1*npparts0

y=y.tolist()
y.sort()
y=np.array(y)
z2=sum(data*y)

print(max(z1,z2))
### BUGGY CODE ###

n=int(input())
a=[int(_) for _ in input().split()]
ans=[]
for i in range(n):
	m=min(a)
	ans.append(str(a.index(m)+1))
	a[a.index(m)]=10**6
print(' '.join(ans))

### FIXED CODE ###

n=int(input())
a=[int(_) for _ in input().split()]
ans=[0]*n
for i in range(n):
	ans[a[i]-1]=i+1
print(' '.join(map(str,ans)))
### BUGGY CODE ###

from sys import exit, setrecursionlimit


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


def dfs(node_id, edges, dp):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges, dp)
        if t == 0:  # looped
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


setrecursionlimit(1000000)

N = int(input())
A = [[int(e) - 1 for e in input().split()] for _ in range(N)]

node_id_db = [[0] * N for _ in range(N)]
v = 0
for i in range(N):
    for j in range(i + 1, N):
        node_id_db[i][j] = v
        v += 1

start_nodes = []
edges = [[] for _ in range(N * (N - 1) // 2)]
for i in range(N):
    Ai = A[i]
    from_id = get_node_id(i, Ai[0], node_id_db)
    if i < Ai[0]:
        start_nodes.append(from_id)
    for j in range(1, N - 1):
        to_id = get_node_id(i, Ai[j], node_id_db)
        edges[from_id].append(to_id)
        from_id = to_id

dp = [-1] * (N * (N - 1) // 2)
print(max(dfs(n, edges, dp) for n in start_nodes))


### FIXED CODE ###

from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 0
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    if res > t:
      t = res
  t += 1
  dp[v] = t
  return t

def toId(i, j, id_db):
  if i < j:
    return id_db[i][j]
  else:
    return id_db[j][i]

def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

  id_db = [[0] * N for _ in range(N)]

  dp = [-1] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(i + 1, N):
      id_db[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id_db)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()
### BUGGY CODE ###

def exp(x):
  ans = 0
  for i in range(x+1):
    ans += i
  return ans / x

n, k = map(int, input().split())
p = list(map(int, input().split()))
  
sum = 0
ans = []
for i in range(k):
  sum += exp(p[i])
ans.append(sum)

for i in range(n-k):
  sum -= exp(p[i])
  sum += exp(p[i+k])
  ans.append(sum)

print(max(ans))

### FIXED CODE ###

def exp(x):
  return (1+x) / 2

n, k = map(int, input().split())
p = list(map(int, input().split()))
  
sum = 0
for i in range(k):
  sum += exp(p[i])
max = sum

for i in range(n-k):
  sum += exp(p[i+k]) - exp(p[i])
  if max < sum:
    max = sum

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

N = int(input())
lst = list(map(int,input().split()))
lst2 = []
for i in lst:
  lst2.append(i)
  lst2.reverse()
print(" ".join(map(str,lst2)))

### FIXED CODE ###

N = int(input())
lst = list(map(int,input().split()))
lst.reverse()
lst2 = [0] * N
for idx,i in enumerate(lst):
  if (idx % 2 == 0):
    lst2[idx // 2] = i
  else:
    lst2[N-(idx // 2)-1] = i
print(" ".join(map(str,lst2)))
### BUGGY CODE ###

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

for a in A:
    if a in d:
        d[a]+=1
    else:
        d[a]=1
        
if 1 in d:
    if d[1]==1:
        ans=1
    else:
        ans=0

else:
    ans=0
    for i in d:
        p=1
        if d[i]>1:
            continue
        for j in range(2,int(i**0.5)+1):
            if i%j==0:
                if j in d or i//j in d:
                    p=0
                    break
        ans+=p

print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
M=max(A)+1
table=[0 for _ in range(M)]

for i in range(N):
    if i>0 and A[i]==A[i-1]:
        table[A[i]]=0
        continue
    table[A[i]]=1
    for n in range(2,M):
        if A[i]*n>=M:
            break
        table[A[i]*n]=0
print(sum(table))
### BUGGY CODE ###

S = input()
Q = int(input())

S_list = list(S)

for i in range(Q):
    Query = input()
    #Query = Query.replace(' ', '')
    #Query = list(Query)
    T, F, C = 0, 0, ''
    if Query[0] == '2':
        T = int(Query[0])
        F = int(Query[2])
        C = Query[4]
    else:
        T = int(Query[0])
    
    if T == 1:
        S_list = S_list[::-1]
        
    if T == 2:
        if F == 1:
            S_list.insert(0, C)
        else:
            S_list.append(C)
            
print(''.join(S_list))

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

S_list = list(S)

r = 1
a = []
b = []
d = deque(a)

for i in range(Q):
    q = input().split()
    if q[0] == '1':
        r *= -1
        continue
    elif len(q) == 3:
        if q[1] == '1':
            if r == -1:
                b.append(q[2])
            else:
                d.appendleft(q[2])
        else:
            if r == -1:
                d.appendleft(q[2])
            else:
                b.append(q[2])
                
answer = list(d) + S_list + b

if r == -1:
    answer = answer[::-1]
    
print(''.join(answer))
### BUGGY CODE ###

L = int(input())
ans = [0]
for i in range(1, 350):
    for j in range(1, 350):
        for k in range(1, 350):
            if i + j + k == L:
                ans.append(i*j*k)
print(max(ans))

### FIXED CODE ###

L = int(input())

a=b=c=L/3
print(a*b*c)
### BUGGY CODE ###

def test():
    n=int(input())
    a=list(map(int,input().split()))
    b=[]
    for i in range(n):
        b.append(a[i])
        b.reverse()
    return " ".join(map(str,b))
t=test()
print(t)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.reverse()
ans=[]
re_ans=[]
if n==1:
    print(a[0])
else:
    ans=a[::2]
    re_ans=a[1::2]
    re_ans.reverse()
    ans.extend(re_ans)
    map_ans=map(str,ans)
    v=" ".join(map_ans)
    print(v)
### BUGGY CODE ###

N = int(input())
L_list = sorted([int(x) for x in input().split()])
cnt = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            a, b, c = L_list[i], L_list[j], L_list[k]
            if (c < a+b):
                cnt += 1
            else:
                break
print(cnt)


### FIXED CODE ###

import bisect
N = int(input())
L = sorted([int(x) for x in input().split()])
cnt = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        cnt +=  bisect.bisect_left(L, L[i]+L[j]) - (j+1)
print(cnt)
### BUGGY CODE ###

def main():
    s = input()
    t = input()

    len_s = len(s)
    len_t = len(t)

    DP = [[0] * (len_t + 1) for _ in range(len_s + 1)]

    for i in range(len_s):
        for j in range(len_t):
            if s[i] == t[j]:
                DP[i + 1][j + 1] = DP[i][j] + 1
            else:
                DP[i + 1][j + 1] = max(DP[i + 1][j], DP[i][j + 1])

    ans = ""
    i = len_s
    j = len_t
    while DP[i][j]:
        if s[i - 1] == t[j - 1]:
            ans += s[i - 1]
            i -= 1
            j -= 1
        else:
            if DP[i - 1][j] > DP[i][j -1]:
                i -= 1
            else:
                j -= 1

    print(ans[::-1])


if __name__ == '__main__':
    main()

exit()

### FIXED CODE ###

def main():
    s = input()
    t = input()

    len_s = len(s)
    len_t = len(t)

    DP = [[0] * (len_t + 1) for _ in range(len_s + 1)]

    for i in range(len_s):
        for j in range(len_t):
            if s[i] == t[j]:
                DP[i + 1][j + 1] = DP[i][j] + 1
            else:
                DP[i + 1][j + 1] = max(DP[i + 1][j], DP[i][j + 1])

    ans = ""
    i = len_s
    j = len_t
    while DP[i][j]:
        if s[i - 1] == t[j - 1]:
            ans += s[i - 1]
            i -= 1
            j -= 1
        else:
            if DP[i - 1][j] > DP[i][j -1]:
                i -= 1
            else:
                j -= 1

    print(ans[::-1])


if __name__ == '__main__':
    main()

exit()
### BUGGY CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
INF=10**9
add_list=[INF]*K

H.extend(add_list)

dp=[INF]*(N+100) #Kの分追加
dp[0]=0
for n in range(N):
    for k in range(1,K+1):
        dp[n+k]=min(dp[n+k], dp[n]+abs(H[n]-H[n+k]))
print(dp[N-1])

### FIXED CODE ###

# 貰うDP
N,K=map(int,input().split())
h=list(map(int,input().split()))
INF=10**9
dp=[INF]*(N)
dp[0]=0

for n in range(1,N):
    dp[n]=min([dp[k] + abs(h[n] - h[k]) for k in range(max(0,n-K), n)])
print(dp[N-1])
### BUGGY CODE ###

from collections import deque
import math

def eratosthenes(limit):
   A=[c for c in range(3,limit+1,2)]
   A.insert(0,2)
   P=deque()

   while True:
      prime_number=A[0]

      if prime_number > math.sqrt(limit):
         break

      P.append(prime_number)

      i=0
      while i < len(A):
         if A[i] % prime_number == 0:
            A.pop(i)
            continue
         i += 1

   for a in A:
      P.append(a)

   li=list(P)
   return(li)

from fractions import gcd
A,B=map(int,input().split())
C=gcd(A,B)
prime_numbers=eratosthenes(C)
count=1

for i in range(1,C+1):
   if C%i==0:
      if i in prime_numbers:
         count+=1

print(count)

### FIXED CODE ###

from fractions import gcd
A,B=map(int,input().split())
C=gcd(A,B)

if C==1:
   print(1)
else:
   count=1
   C_copy=C
   n=2
   while n**2<=C:
      flag=False
      while C_copy%n==0:
         C_copy//=n
         flag=True
      if flag:
         count+=1
         n=n+1 if n==2 else n+2
      else:
         n=n+1 if n==2 else n+2
   
   if C_copy!=1:
      count+=1

   print(count)
### BUGGY CODE ###

n, m = map(int, input().split())
ans = -1
mod = pow(10, 9) + 7

if abs(n-m) > 1:
    ans = 0
else:
    if abs(n-m) == 0:
        a = 1
        for i in range(1, n+1):
            a *= i
        ans = a*a*2
    if abs(n-m) == 1:
        a = 1
        for i in range(1, min(n, m)+1):
            a *= i
        b = a * max(n, m)
        ans = a * b

print(ans%mod)


### FIXED CODE ###

import math
n, m = map(int, input().split())
ans = -1
mod = pow(10, 9) + 7

if abs(n-m) > 1:
    ans = 0
else:
    if abs(n-m) == 0:
        a = math.factorial(n)
        ans = a*a*2
    if abs(n-m) == 1:
        a = math.factorial(min(n, m))
        b = a * max(n, m)
        ans = a * b

print(ans%mod)
### BUGGY CODE ###

n = int(input())
min = n
for i in range(1,n+1):
    if n % i == 0:
        if min > i + n/i-2:
            min = i + n/i -2
        elif min <= i + n/i-2:
            break
print(int(min))

### FIXED CODE ###

import math
n = int(input())
min = n - 1
#√n を算出
split = n / math.sqrt(n)


for i in range(int(split),0,-1):
    if n % i == 0:
        min = i + n/i -2
        break

print(int(min))
### BUGGY CODE ###

num = int(input())
pole_list = sorted([int(item) for item in input().split()])

import numpy as np
pole_list = np.array(pole_list)

cnt = 0

for i in range(num):
    for j in range(i + 1, num):
        cnt += len(np.where(pole_list < pole_list[i] + pole_list[j])[0]) - j - 1
print(cnt)


### FIXED CODE ###

from bisect import bisect_left
 
N = int(input())
Lmat = [int(n) for n in input().split()]
Lmat.sort()
 
sum = 0

for i in range(N):
    for j in range(i + 1, N):
        sum += bisect_left(Lmat, Lmat[i]+Lmat[j]) - (j + 1)
        
print(sum)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 100000000000000
for i in range(n):
  if sum(a[:i]) == sum(a[i:]):
    ans = 0
    break
  elif ans > abs(sum(a[:i]) - sum(a[i:])):
    ans = abs(sum(a[:i]) - sum(a[i:]))
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = sum(a)
al = ans
mod = 0
for i in range(n):
  if mod + a[i] == al - a[i]:
    ans = 0
    break
  elif ans > abs(mod - al + 2*a[i]):
    ans = abs(mod - al + 2*a[i])
    mod += a[i]
    al -= a[i]
  else:
    mod += a[i]
    al -= a[i]
print(ans)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(k) for k in input().split()]
C=[int(h) for h in input().split()]
A.sort()
B.sort()
C.sort()
deli=[]

for i in A:
    for j in B:
        for k in C:
            deli.append(i+j+k)
deli.sort(reverse=True)
for i in range(min(K,X*Y*Z)):
    print(deli[i])

### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=sorted([int(i) for i in input().split()],reverse=True)
B=sorted([int(i) for i in input().split()],reverse=True)
C=sorted([int(i) for i in input().split()],reverse=True)
bi_deli=[]
for i in range(min(X,K)):
    for j in range(min(Y,K)):
        if (i+1)*(j+1)>K:
            break
        bi_deli.append(A[i]+B[j])
bi_deli.sort(reverse=True)
tri_deli=[]
for k in range(min(len(bi_deli),K)):
    for l in range(min(Z,K)):
        if (k+1)*(l+1)>K:
            break
        tri_deli.append(bi_deli[k]+C[l])
tri_deli.sort(reverse=True)

print(*tri_deli[:K],sep='\n')
### BUGGY CODE ###

n = int(input())
a = [float(input()) for _ in range(n)]
b = sorted(a)
for i in range(n):
    print(b.index(a[i]) * 3 + b.count(a[i]) - 1)


### FIXED CODE ###

import bisect
n = int(input())
a = [float(input()) for _ in range(n)]
b = sorted(a)
for i in range(n):
    x = bisect.bisect_left(b, a[i])
    y = bisect.bisect_right(b, a[i])
    print(x * 2 + y - 1)
### BUGGY CODE ###

from collections import deque
s = [input()]
q = int(input())

flag = 0
for i in range(q):
    x = list(input().split())
    if int(x[0]) == 1:
        if flag ==0:
            flag = -1
        else:
            flag = 0
        continue
    if int(x[1]) +flag == 1:
        s2 = deque(s)
        # s.insert(0, x[2])
        s2.appendleft(x[2])
        s = list(s2)
    else:
        s.append(x[2])
ans = ''.join(s)
if flag == -1:
    print(ans[::-1])
else:
    print(ans)

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())

header = []
footer = []
flag = 0
for i in range(q):
    x = list(input().split())
    if int(x[0]) == 1:
        if flag ==0:
            flag = -1
        else:
            flag = 0
        continue
    if int(x[1]) +flag == 1:
        header.append(x[2])
        # s2 = deque(s)
        # # s.insert(0, x[2])
        # s2.appendleft(x[2])
        # s = list(s2)
    else:
        # s.append(x[2])
        footer.append(x[2])
# ans = ''.join(s)
head = ''.join(reversed(header))
ans = head +s + ''.join(footer)
if flag == -1:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+H+1),dtype=np.int64)
R = np.arange(1,H+1)[None,:]
L = np.arange(1,H+1)[:,None]
for r in range(H):
    for l in range(H):
        dp_1[:,r-l+H,r+l+2] = (C[:-1][:,l] == C[1:][:,r])
np.cumsum(dp_1,out=dp_1,axis=2)

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
dp[:,H] = 0
for n in range(1,H+H+1):
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:-1] = np.minimum(dp[:,:-1],prev[:,1:])
    dp += dp_1[:,:,n]
answer = dp[:,H].sum()
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
result = []
for i in range(len(A)):
  if A.count(A[i])%2!=0:
    if i in result:
      A.remove(A[i])
      continue
    result.append(A[i])
  else:
    continue
print(len(result))

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
dict = {}
for i in A:
  if i not in dict:
    dict[i] = 1
  else:
    dict[i] += 1
print(len([1 for i in dict.values() if i%2!=0]))
### BUGGY CODE ###

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

memo = {}
cnt_max = {}
for i in range(n):
    cnt_max[i] = 0
for i in range(n):
    memo[i] = 0

cnt = 0
while True:
    flag = False
    for i in range(n)[::-1]:
        if memo[i] == len(a[0]):
            continue
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            flag = True
            tmp = memo[i]
            max_1 = max(cnt_max[i], cnt_max[a[i][tmp] - 1])
            cnt_max[i] = max_1 + 1
            cnt_max[a[i][tmp] - 1] = max_1 + 1
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print(-1)
                exit()
        break
ans = 0
for i in cnt_max:
    ans = max(cnt_max[i] , ans)
print(ans)


### FIXED CODE ###

import time
s_time = time.time()


n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

memo = {}
for i in range(n):
    memo[i] = 0

cnt = 0
while True:
    visited = [False] * n
    flag = False
    for i in range(n):
        if memo[i] == len(a[0]):
            continue
        if visited[i] or visited[a[i][memo[i]] - 1]:
            continue
        visited[i] = True
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            visited[a[i][memo[i]] - 1] = True
            flag = True
            tmp = memo[i]
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print(-1)
                exit()
        break
    if abs(s_time - time.time()) > 1.7:
        print(n*(n-1) //2)
        exit()
print(cnt)
### BUGGY CODE ###

import bisect
import itertools

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

cnt = 0

for i in range(N):
    L_t = L[i+1:N]
    for v in itertools.combinations(L_t, 2):
        a = int(L[i])
        b = int(v[0])
        c = int(v[1])

        if a < b + c and b < a + c and c < a + b:
            cnt += 1
print(cnt)




### FIXED CODE ###

import bisect
N = int(input())
L = sorted(map(int, input().split()))

cnt = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        ab = L[i] + L[j]
        c_index = bisect.bisect_left(L, ab)
        cnt += c_index - 1 - j
print(cnt)
### BUGGY CODE ###

a = [[0]*3005 for _ in range(3005)]
dp = [[[0]*4 for _ in range(3005)] for _ in range(3005)]
R, C, K = map(int, input().split())
for i in range(K):
    r, c, v = map(int, input().split())
    a[r-1][c-1] = v

for i in range(R):
    for j in range(C):
        for k in range(2, -1, -1):
            dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k]+a[i][j])
        for k in range(4):
            dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k])
            dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k])

ans = 0
for i in range(4):
    ans = max(ans, dp[R-1][C-1][i])
print(ans)



### FIXED CODE ###

r,c,k = list(map(int, input().split()))
import copy
dp=[[[0]*4 for _ in range(c)] for _ in range(2)]


F = [[0]*c for _ in range(r)]

for _ in range(k):
  x,y,v = list(map(int, input().split()))
  x-=1
  y-=1
  F[x][y] = v
  
for nn in range(r):
  for j in range(c):
    i = 1
    val = F[nn][j]
  
      
    mxv = max(dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2], dp[i-1][j][3])

    dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2] + val)
    dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1] + val)
    dp[i][j][1] = max(dp[i][j-1][1], dp[i][j-1][0] + val, mxv + val)
    dp[i][j][0] = mxv

  dp[0] = dp[1] 
  dp[1] = [[0]*4 for _ in range(c)]

best = 0


for k in range(4):
  best = max(best, dp[0][c-1][k])
    
print(best)