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

def bin_search1(L1,L2,l):#長すぎる辺の個数を返す
    low = 0
    high = len(l)-1
    while high-low>1:
        mid = (low+high)//2
        if (L1+L2<=l[mid]):#長すぎ
            high = mid
        else:
            low = mid
    if L1+L2>l[high]:#全部ok
        return 0
    elif L1+L2<=l[low]:#全部ng
        return len(l)
    else:
        return len(l)-high

def bin_search2(L1,L2,l):#短すぎる辺の個数を返す
    low = 0
    high = len(l)-1
    while high-low>1:
        mid = (low+high)//2
        if (abs(L1-L2)>=l[mid]):
            low = mid
        else:
            high = mid
    if abs(L1-L2)<l[low]:
        return 0
    elif abs(L1-L2)>=l[high]:
        return len(l)
    else:
        return high

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

ans = 0

for i in range(N):
    for j in range(N):
        if i!=j:
            L_temp = L#修正面倒なため
            a = L[i]
            b = L[j]
            if i<j:
                L_temp.pop(j)
                L_temp.pop(i)
                ans += (N-2-bin_search1(a,b,L_temp)-bin_search2(a,b,L_temp))
                L.insert(i,a)
                L.insert(j,b)
            else:
                L_temp.pop(i)
                L_temp.pop(j)
                ans += (N-2-bin_search1(a,b,L_temp)-bin_search2(a,b,L_temp))
                L.insert(j,b)
                L.insert(i,a)

           
         
        
ans = ans//6

print(ans)

### FIXED CODE ###

from bisect import bisect＿left

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

ans = 0

for i in range(N-1):
    for j in range(i+1,N):
        ans += bisect_left(L,L[i]+L[j])-(j+1)

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

N, K = map(int,input().split())
sett = set()
ans = float('inf')
while N not in sett:
  sett.add(N)
  N = abs(N-K)
  ans = min(ans,N)
print(ans)

### FIXED CODE ###

def main():
  N, K = map(int,input().split())
  print(min(N%K, K-N%K))
  return 
main()
### BUGGY CODE ###

#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [input() for _ in range(n)]


import itertools

n = int(input())
seq = list(map(int, input().split()))

ans = 0
a = list(itertools.combinations(seq,2))

for i in range(len(a)):
    #print(a[i][0], a[i][1])
    ans += a[i][0] * a[i][1]
    ans %= 10**9+7


print(ans)



### FIXED CODE ###

#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [input() for _ in range(n)]


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

s = 0
for i in range(N):
    s += seq[i]

s2 =0
for i in range(N):
    s2 += seq[i]**2


s0 = (s**2 -s2)//2

print(s0%(10**9+7))
### BUGGY CODE ###

N, K = map(int, input().split())
l = list(map(int, input().split()))
first = True
for i in range(K+1):
  s = 0
  
  for j in l:
    s += i ^ j
    
  if first:
    m = s
    first = False
  else:
    if m < s:
      m = s
print(m)

### FIXED CODE ###

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

max_bit = 40
ans = 0
for i in range(max_bit, -1, -1):
  bit = 2 ** i
  c = len([1 for j in a if j&bit > 0])
  if 2*c < N and bit <= K:
    c = N - c
    K -= bit
  ans += bit * c
print(ans)
### BUGGY CODE ###

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

m = 0
for i in range(len(l)-(K-1)):
    if l[i] < l[i-1]:
        continue
    elif m < sum(l[i:i+K]):
        m = sum(l[i:i+K])
        t = l[i:i+K]
        
def E(n):
    return sum(range(1,n+1)) / n

l2 = list(map(E, t))

print(sum(l2))

### FIXED CODE ###

N,K = map(int, input().split())
l = list(map(int,input().split()))
 
def E(n):
  return (1 + n) / 2
 
j = sum(l[0:0+K])
m = 0
if N == 1:
  l2 = list(map(E, l))
  print(sum(l2))
elif N == K:
  l2 = list(map(E, l))  
  print(sum(l2))
else:
  for i in range(1,len(l)-(K-1)):
      j = j - l[i-1] + l[i+K-1]
      if l[i] < l[i-1]:
          continue
      elif m < j:
          m = j
          t = l[i:i+K]

  l2 = list(map(E, t))
 
  print(sum(l2))
### BUGGY CODE ###

import numpy as np


def count_multi(s, d):
  a = np.array([int(c) for c in s], dtype=np.uint16)
  # assume d >= 10
  m = a
  # s not include 0
  count = 0
  while len(m) > 1:
    a = a[1:]
    m = (m[:-1]*10 + a) % d
    count += np.count_nonzero(m == 0)
  return count

print(count_multi(input().strip(), 2019))


### FIXED CODE ###

def main():
    mod = 2019
    count = [0] * 2019
    count[0] = 1
    s = input().strip()
    digit = 1
    current = 0
    for c in s[::-1]:
        current = (current + int(c) * digit) % mod
        count[current] += 1
        digit = digit * 10 % mod
    return sum([n * (n - 1) // 2 for n in count if n > 1])


print(main())
### BUGGY CODE ###

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

if (b-a)%2==0:
    print((b-a)//2)
else:
    if n >= 10**5:
        if a < math.floor(n/2):
            i = 0
            while True:
                b -= i
                if a <= 1:
                    a = 1
                else:
                    a -= i
                if a == b:
                    a += 10000
                    b += 10000
                    for j in range(1,10001):
                        a -= j
                        b -= j
                        if a <= 1:
                            a = 1
                        if a == b:
                            print(i+j)
                            break
                    break
                i += 10000
        else:
            i = 0
            while True:
                a += i
                if b >= n:
                    b = n
                else:
                    b += i
                if a == b:
                    a -= 10000
                    b -= 10000
                    for j in range(1,10001):
                        a += j
                        b += j
                        if b >= n:
                            b = n
                        if a == b:
                            print(i+j)
                            break
                    break
                i += 10000
    else:
        if a < math.floor(n/2):
            i = 0
            while True:
                b -= i
                if a <= 1:
                    a = 1
                else:
                    a -= i
                if a == b:
                    print(i)
                    break
                i += 1
        else:
            i = 0
            while True:
                a += i
                if b >= n:
                    b = n
                else:
                    b += i
                if a == b:
                    print(i)
                    break
                i += 1
    
#min  median max

### FIXED CODE ###

n,a,b = map(int,input().split())
i = 1
p = 0
if (b-a)%2==0:
    print((b-a)//2)
else:
    if a-1 < n-b:
        print(min((1+b+(a-2))//2,b-1))
    else:
        print(min((n-a+(n-b+1))//2,n-a))
### BUGGY CODE ###

N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
    w,v = wv[i]
    for j in range(1,W+1):
        if j >= w:
            DP[i+1][j] = max(DP[i][j-w]+v,DP[i][j],DP[i+1][j-1])
        else:
            DP[i+1][j] = max(DP[i][j],DP[i+1][j-1])
print(DP[-1][-1])

### FIXED CODE ###

N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
    w,v = wv[i]
    for j in range(1,W+1):
        if j >= w:
            DP[i+1][j] = max(DP[i][j-w]+v,DP[i][j],DP[i+1][j-1])
        else:
            DP[i+1][j] = max(DP[i][j],DP[i+1][j-1])
print(DP[-1][-1])
### BUGGY CODE ###

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

tmp = 1
for i in range(k):
    tmp *= a[i]

for i in range(k, n):
    tmp2 = tmp * a[i] // a[i - k]
    if tmp2 > tmp:
        print("Yes")
    else:
        print("No")
    tmp = tmp2

### FIXED CODE ###

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

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

import itertools
x = int(input())
if x>=2000:
  print(1)
  exit()
else:
  l = list(range(20))
  for nums in itertools.product(l,repeat=6):
    t = nums[0]*100+nums[1]*101+nums[2]*102+nums[3]*103+nums[4]*104+nums[5]*105
    if t==x:
      print(1)
      exit()
print(0)

### FIXED CODE ###

x = int(input())

c = x//100

if c*100<=x and x<=c*105:
  print(1)
else:
  print(0)
### BUGGY CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k = na()
p = na()
c = na()

s = set(range(n))

ans = 0
loops = []
while s:
    loop = [0]
    a = s.pop()
    while True:
        loop.append(loop[-1]+c[p[a]-1])
        if p[a]-1 not in s:
            break
        a = p[a]-1
        s.discard(a)
    loops.append(loop[1:])

ans = -1000000000000000
for tmp in loops:
    kk = k
    if k > len(tmp): kk = k%len(tmp)+len(tmp)
    loop = [0]+tmp+[tmp[-1]+u for u in tmp]+[tmp[-1]*2+u for u in tmp]
    x = -1000000000000
    for i in range(1,kk+1):
        for j in range(len(tmp)+1):
            x = max(x,loop[j+i]-loop[j])
    if k > len(tmp) and tmp[-1] > 0:
        x += tmp[-1]*(k//len(tmp)-1)
    ans = max(ans,x)

print(ans)


### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k = na()
p = na()
c = na()

s = set(range(n))

ans = 0
loops = []
while s:
    loop = [0]
    a = s.pop()
    while True:
        loop.append(loop[-1]+c[p[a]-1])
        if p[a]-1 not in s:
            break
        a = p[a]-1
        s.discard(a)
    loops.append(loop[1:])

ans = -1000000000000000
for tmp in loops:
    kk = k
    if k > len(tmp): kk = k%len(tmp)+len(tmp)
    loop = [0]+tmp+[tmp[-1]+u for u in tmp]+[tmp[-1]*2+u for u in tmp]
    x = -1000000000000
    for i in range(1,kk+1):
        for j in range(len(tmp)+1):
            x = max(x,loop[j+i]-loop[j])
    if k > len(tmp) and tmp[-1] > 0:
        x += tmp[-1]*(k//len(tmp)-1)
    ans = max(ans,x)

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

#Reference : http://qiita.com/lethe2211/items/6cbade2bc547649bc040
n = input()

R = []
for i in range(n):
    R.append(input())
gain_list = []
for i in range(n):
    gain_list.append(-pow(10, 9))

start_point = 0
peak = 0

while (start_point < n - 1):
    for i in range(start_point + 1, n):
         diff = R[i] - R[start_point]
         if (diff >= gain_list[start_point]):
             gain_list[start_point] = diff
             peak = i
    for i in range(start_point, peak):
        gain_list[i] = R[peak] - R[i]
    start_point = peak

print max(gain_list)

### FIXED CODE ###

#Reference : http://qiita.com/lethe2211/items/6cbade2bc547649bc040
#Reference : http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=ALDS1_1_D
n = input()

R = []
for i in range(n):
    R.append(input())

min_v = R[0]
max_v = -pow(10, 9)
for i in range(1, n):
    temp = R[i] - min_v
    if (temp >= max_v):
        max_v = temp
    temp = R[i]
    if (min_v >= temp):
        min_v = temp
print max_v
### BUGGY CODE ###

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

def solve(i, m):
    if m == 0:
        return True
    if i >= n:
        return False
    res = solve(i + 1, m) or solve(i + 1, m - A[i])
    return res
for m in M:
    if solve(0, m):
        print('yes')
    else:
        print('no')

### FIXED CODE ###

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

memo = {}
def solve(i, m):
    if m == 0:
        return True
    if i >= n:
        return False
    if memo.get((i, m), None) == None:
        memo[(i, m)] = solve(i + 1, m) or solve(i + 1, m - A[i])
    return memo[(i, m)]
for m in M:
    if solve(0, m):
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

# cook your dish here

num = int(input())
arr = list(map(int,input().split(" ")));

maxi = 1000000000000000000
val = 1;
for i in arr:
        val = val*i;

if val>maxi:
        print("-1")
else:
        print(val)
        

### FIXED CODE ###

# cook your dish here

num = int(input())
arr = list(map(int,input().split(" ")));

maxi = 1000000000000000000

val = 1;
arr.sort()

if arr[0]==0:
        print(0)

else:
        for i in arr:
                val = val*i;
                if val>maxi:
                        val = -1
                        break
        
        
        print(val)
### BUGGY CODE ###

s = input()
t = input()
a = len(list(s))
b = len(list(t))
#dp[i][j] をsをi番目、ｔをj番目までの最長共通長
INF = float('inf')
dp = [[-INF for j in range(b+1)] for i in range(a+1)]
for i in range(a+1):
    dp[i][0] = 0
for j in range(b+1):
    dp[0][j] = 0
for i, x in enumerate(list(s)):
    for j, y in enumerate(list(t)):
        if x == y:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
#復元パート
ans = ''
while a > 0 and b >0:

    if dp[a][b] == dp[a-1][b]:
        a -= 1
    elif dp[a][b] == dp[a][b-1]:
        b -= 1
    else:
        ans = list(s)[a-1] + ans
        a -= 1
        b -= 1
print(ans)

### FIXED CODE ###

s = input()
t = input()
a = len(list(s))
b = len(list(t))
#dp[i][j] をsをi番目、ｔをj番目までの最長共通長
INF = float('inf')
dp = [[-INF for j in range(b+1)] for i in range(a+1)]
for i in range(a+1):
    dp[i][0] = 0
for j in range(b+1):
    dp[0][j] = 0
for i, x in enumerate(list(s)):
    for j, y in enumerate(list(t)):
        if x == y:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
#復元パート
ans = ''
while a > 0 and b >0:

    if dp[a][b] == dp[a-1][b]:
        a -= 1
    elif dp[a][b] == dp[a][b-1]:
        b -= 1
    else:
        ans = list(s)[a-1] + ans
        a -= 1
        b -= 1
print(ans)
### BUGGY CODE ###

n=100000
n=long(raw_input(""))
fact=1
for i in range(1,n+1):
    fact*=i
print (fact%((10**9)+7))    

### FIXED CODE ###

import math
x = int(input())
print(math.factorial(x) % (10**9 + 7))
### BUGGY CODE ###

import sys

input = sys.stdin.readline

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

dp = [sys.maxsize] * N

dp[0] = 0

for i in range(1, N):
    for j in range(1, K+1):
        if i >= j:
            dp[i] = min(dp[i], dp[i - j] + abs(h[i - j] - h[i]))

print(dp[N - 1])


### FIXED CODE ###

import sys
import numpy as np

input = sys.stdin.readline

N, K = map(int, input().split())
h = np.array(list(map(int, (input().split()))))

dp = np.full(N,sys.maxsize,dtype=int)

dp[0] = 0

for i in range(1, N):
    s = max(0, i - K)
    dp[i] = min(dp[s:i] + abs(h[i] - h[s:i]))

print(dp[N - 1])
### BUGGY CODE ###

for e in iter(input,'0 0'):
 H,W=map(int,e.split())
 s=[[*map(int,input().split())]for _ in[0]*H]
 a=0
 for x in range(2**H):
     t=[[c^(1>>b&x)for c in r]for r,b in zip(s,range(H))]
     a=max(a,sum(max(sum(c),H-sum(c))for c in zip(*t)))
 print(a)


### FIXED CODE ###

def v():
 for e in iter(input,'0 0'):
  r=int(e.split()[0])
  d=[int(''.join(x),2)for x in zip(*[input().split()for _ in[0]*r])]
  a=0
  for m in range(1<<~-r):
   t=0
   for s in d:
    c=bin(m^s).count('1')
    t+=max(c,r-c)
   if a<t:a=t
  print(a)
if'__main__'==__name__:v()
### BUGGY CODE ###

N = int(input())
A = sorted((map(int,input().split())))
B = [True]*N

for i in range(N):
    if B[i]:
        for j in range(i, N):
            if B[j] and j != i:
                if A[j] == A[i]:
                    B[i] = False
                    B[j] = False
                elif A[j] % A[i] == 0:
                    B[j] = False
ans = 0
for i in range(N):
    if B[i]:
        ans += 1

print(ans)



### FIXED CODE ###

N = int(input())
A = sorted((map(int,input().split())))
a_Max = A[-1]
B = [0]*a_Max

for a in A:
    if B[a-1] == 0:
        B[a-1] = 1
        for j in range(2,a_Max+1):
            if a*j > a_Max:
                break
            B[a*j-1] = 2
    elif B[a-1] == 1:
        B[a-1] = 2
            
ans = 0
for b in B:
    if b == 1:
        ans += 1

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

n,m=map(int,input().split())
H=list(map(int,input().split()))
M=[]
L=[[]]*(n+1)
for i in range(m):
	a,b=map(int,input().split())
	M.append([a,b])
	L[a] = L[a]+[b]
	L[b] = L[b]+[a]
	
#print(L)

flag=0
for i in range(1,len(L)):
	count=0
	if L[i]!=[]:
		for j in list(set(L[i])):
			if H[j-1]>=H[i-1]:
				break
			else:
				count+=1
		if count==len(set(L[i])):
			flag+=1
	else:
		flag+=1
print(flag)

### FIXED CODE ###

from sys import stdin,stdout
n,m=map(int,stdin.readline().split())
H=list(map(int,stdin.readline().split()))
L=[0]*n
for i in range(m):
	a,b=map(int,stdin.readline().split())
	L[a-1]=max(L[a-1],H[b-1])
	L[b-1]=max(L[b-1],H[a-1])
ans=0
for i in range(n):
	if H[i]>L[i]:
		ans+=1
		
stdout.write(str(ans))
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0

for i in range(n):
    for j in range(i,n):
        for k in range(j,n):
            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i] and j-i != k-j:
                ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
s = input()

r_cnt = s.count('R')
g_cnt = s.count('G')
b_cnt = s.count('B')

# print(r_cnt, g_cnt, b_cnt)
ans = r_cnt * g_cnt * b_cnt
# print(ans)

for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        # print(i,j,k)
        if k >= n: 
            # print('/')
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            ans -= 1

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

N = int(input())
S = list(map(int, input().split()))
S.sort()
ans = 0
if N > 1:
    if S[0] < S[1]:
        ans += 1
else:
    ans = 1
for i in range(N-1, 0, -1):
    num = S[i]
    M = num//2
    flg = True
    for j in range(i):
        if num%S[j] == 0:
            flg = False
            break
        elif S[j] > M:
            break
    if num == S[i-1]:
        flg = False
    elif i < N-1:
        if num == S[i+1]:
            flg = False
    if flg:
        ans += 1
print(ans)

        
    

### FIXED CODE ###

N = int(input())
S = list(map(int, input().split()))
S.sort()

ans = 0
A = [True]*(10**6+1)

for i in range(0, N):
    if not A[S[i]]:
        continue
    if 0 < i:
        if S[i-1] == S[i]:
            continue
    if i < N-1:
        if S[i] == S[i+1]:
            for j in range(1, 10**6//S[i]+1):
                A[S[i]*j] = False
            continue
    ans += 1
    for j in range(1, 10**6//S[i]+1):
        A[S[i]*j] = False

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

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *XYH = map(int, read().split())

    for cx in range(101):
        for cy in range(101):
            ok = 10 ** 12
            ng = 0
            while ok - ng > 1:
                mid = (ok + ng) // 2
                valid = True
                for x, y, h in zip(*[iter(XYH)] * 3):
                    if max(mid - abs(x - cx) - abs(y - cy), 0) < h:
                        valid = False
                        break
                if valid:
                    ok = mid
                else:
                    ng = mid
            H = ok
            valid = True
            for x, y, h in zip(*[iter(XYH)] * 3):
                if max(H - abs(x - cx) - abs(y - cy), 0) != h:
                    valid = False
                    break
            if valid:
                print(cx, cy, H)
                return

    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *XYH = map(int, read().split())

    for cx in range(101):
        for cy in range(101):
            ok = 10 ** 9 + 100
            ng = 0
            while ok - ng > 1:
                mid = (ok + ng) // 2
                valid = True
                for x, y, h in zip(*[iter(XYH)] * 3):
                    if max(mid - abs(x - cx) - abs(y - cy), 0) < h:
                        valid = False
                        break
                if valid:
                    ok = mid
                else:
                    ng = mid
            H = ok
            valid = True
            for x, y, h in zip(*[iter(XYH)] * 3):
                if max(H - abs(x - cx) - abs(y - cy), 0) != h:
                    valid = False
                    break
            if valid:
                print(cx, cy, H)
                return

    return


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

from itertools import accumulate
N, M, K = map(int,input().split())
A_list = [0] + list(map(int,input().split()))
B_list = [0] + list(map(int,input().split()))
A_sums_list = list(accumulate(A_list))
B_sums_list = list(accumulate(B_list))

for n in range(N + 1):
    if A_sums_list[n] > K:
        break
    A_max = n
for m in range(M + 1):
    if B_sums_list[m] > K:
        break
    B_max = m
ans = max(A_max, B_max)

for i in range(A_max + 1):
    for j in reversed(range(B_max + 1)):
        if i + j > ans:
            if A_sums_list[i] + B_sums_list[j] <= K:
                ans = i + j
        else:
            break
print(ans)

### FIXED CODE ###

import itertools
n, m, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))

sa = list(itertools.accumulate(a))
sb = list(itertools.accumulate(b))

output = 0
j = m
for i in range(n + 1):
    if sa[i] > k:
        break
    while sa[i] + sb[j] > k:
        j -= 1
    if output < i + j:
        output = i + j
print(output)
### BUGGY CODE ###


from collections import defaultdict

R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]

items = defaultdict(int)
for r, c, v in X:
    items[(r, c)] = v

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

            # Vertical
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][k])

        for k in reversed(range(4)):
            if items[(i, j)] > 0 and k < 3:
                dp[i][j][k + 1] = max(
                    dp[i][j][k + 1], dp[i][j][k] + items[(i, j)])

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


### FIXED CODE ###


R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[r][c] = v

dp = [[0] * 4 for _ in range(C + 1)]
for i in range(1, R + 1):
    # Vertical transition
    for j in range(1, C + 1):
        dp[j][0] = max(dp[j])
        for k in range(1, 4):
            dp[j][k] = 0

    # Horizontal or picking-up transition
    for j in range(1, C + 1):
        for k in reversed(range(4)):
            dp[j][k] = max(dp[j][k], dp[j - 1][k])
            if items[i][j] and k < 3:
                dp[j][k + 1] = max(dp[j][k + 1], dp[j][k] + items[i][j])

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

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

A.sort()

for i in range(1, N+1):
    print(A.count(i))
    A = A[A.count(i):]

### FIXED CODE ###

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

import collections
c = collections.Counter(A)

for i in range(1, N+1):
    print(c[i])
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = int(1e9)

if N == 2:
    print(abs(a[0] - a[1]))
    exit()

for i in range(1, N-1):
    xtemp = sum(a[:i])
    ytemp = sum(a[i:])
    ans = min(ans, abs(xtemp - ytemp))

print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
sa = [a[0]]
for i in range(1, N):
    sa.append(sa[-1] + a[i])

ans = int(1e20)
for i in range(N-1):
    ans = min(ans, abs(sa[i] - (sa[-1] - sa[i])))
print(ans)