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

#!/usr/bin/env python3
#ABC67 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(input())
g = [[] for _ in range(n)]
w = [[float('inf')]*n for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    w[a-1][b-1] = 1
    w[b-1][a-1] = 1

def dijkstra(s,n,w):
    dist = [float('inf')]*n
    used = [False]*n
    dist[s] = 0
    while 1:
        v = -1
        for i in range(n):
            if not used[i] and v == -1:
                v = i
            elif not used[i] and dist[i] < dist[v]:
                v = i
        if v == -1:
            break
        used[v] = True

        for j in range(n):
            dist[j] = min(dist[j],dist[v] + w[v][j])
    return dist

white,black = 0,0
for i in range(n):
    d = dijkstra(i,n,w)
    if d[0] <= d[n-1]:
        black += 1
    else:
        white += 1
if black > white:
    print('Fennec')
else:
    print('Snuke')


### FIXED CODE ###

#!/usr/bin/env python3
#ABC67 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(input())
g = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

que = deque()
que.append((0,0))
c1 = [False]*n
dist1 = [float('inf')]*n
while que:
    d,v = que.popleft()
    dist1[v] = min(dist1[v],d)
    if not c1[v]:
        c1[v] = True
        for u in g[v]:
            que.append((d+1,u))
que = deque()
que.append((0,n-1))
c2 = [False]*n
dist2 = [float('inf')]*n
while que:
    d,v = que.popleft()
    dist2[v] = min(dist2[v],d)
    if not c2[v]:
        c2[v] = True
        for u in g[v]:
            que.append((d+1,u))

w,b = 0,0
for i in range(n):
    if dist1[i] <= dist2[i]:
        b += 1
    else:
        w += 1
if w < b:
    print('Fennec')
else:
    print('Snuke')
### BUGGY CODE ###

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

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

### FIXED CODE ###

N = int(input())
A = list( map( int, input().split() ) )
 
ans = [ 0 for i in range(N) ]

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

for i in ans:
  print(i)
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
ans = 0
start = []

def bfs(y, x):
  q = deque([(y, x)])
  searched = [[0 for _ in range(w)] for _ in range(h)]
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      if 0 <= y+dy < h and 0 <= x+dx < w and searched[y+dy][x+dx] == 0 and a[y+dy][x+dx] == '.':
        searched[y+dy][x+dx] = 1
        q.append([y+dy, x+dx])
        cnt[y+dy][x+dx] = min(cnt[y+dy][x+dx], cnt[y][x]+1)

for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      start.append([i, j])
      cnt[i][j] = 0
      
for i, j in start:
  bfs(i, j)

for i in range(h):
  for j in range(w):
    ans = max(ans, cnt[i][j])


print(ans)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
ans = 0
searched = [[0 for _ in range(w)] for _ in range(h)]
q = deque([])

def bfs():
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      next_y = y + dy
      next_x = x + dx 
      if 0 <= next_y < h and 0 <= next_x < w and searched[next_y][next_x] == 0 and a[next_y][next_x] == '.' and cnt[next_y][next_x] > cnt[y][x]+1:
        searched[next_y][next_x] = 1
        q.append([next_y, next_x])
        cnt[next_y][next_x] = cnt[y][x]+1

for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      cnt[i][j] = 0
      searched[i][j] = 1
      q.append([i, j])

bfs()
for i in range(h):
  for j in range(w):
    ans = max(ans, cnt[i][j])

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

n = int(input())
alist = list(map(int,input().split()))
wa = 0
answer = 0
for i in range(n):
    for j in range(n-i-1):
        wa += alist[i+j+1]
    wa = wa % (10**9 + 7)
    answer += wa * alist[i]
    answer = answer % (10**9 + 7)
    wa = 0
print(answer)

### FIXED CODE ###

n = int(input())
alist = list(map(int,input().split()))
wa = sum(alist)
answer = 0
atai = wa
for i in range(n):
    atai -= alist[i]
    answer += atai * alist[i]
    answer = answer % (10**9 + 7)
print(answer)
### BUGGY CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for i in range(N)]
seen = [0]*N
for val in AB:
    x, y = val
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
#print(dijkstra_heap(0))

lenedge = [len(val) for val in edge]
mledge = max(lenedge)
root = lenedge.index(mledge)
print(mledge)

color = [[0]*N for _ in range(N)]
color_set = set(range(1, mledge+1))

stack = deque()
stack.append([root])
while stack[0]:
    nstack = []
    cstack = stack.pop()
    #print('cstack:', cstack)
    for index in cstack:
        seen[index] = 1
        for edgei in edge[index]:
            if seen[edgei] == 0:
                nstack.append(edgei)
                ncolor = (color_set - set(color[index])).pop()
                color[edgei][index] = ncolor
                color[index][edgei] = ncolor
    stack.append(nstack)

#pri(color)

for ab in AB:
    a, b = ab
    print(color[a-1][b-1])


### FIXED CODE ###

#import numpy as np
from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
#AB = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for i in range(N)]
seen = [0]*N
colors = [0]*(N-1)
#for val in AB:
for i in range(N-1):
    x, y = list(map(int, input().split()))
    edge[x-1].append((i, y-1))
    edge[y-1].append((i, x-1))

lenedge = [len(val) for val in edge]
mledge = max(lenedge)
root = lenedge.index(mledge)
print(mledge)


que = deque()
que.append([(root, -1)])
while que[0]:
    nque = []
    cque = que.popleft()
    #print('cstack:', cstack)
    for tupl in cque:
        index, pcolor = tupl
        seen[index] = 1
        color = 1
        if (color == pcolor): color += 1
        for tupl2 in edge[index]:
            findex, edgei = tupl2
            if seen[edgei] == 0:
                nque.append((edgei, color))
                colors[findex] = color
                color += 1
                if (color == pcolor): color += 1
    que.append(nque)

#pri(color)

for color in colors:
    print(color)
### BUGGY CODE ###

a = [ int(i) for i in input().split()]

b = (a[0]*a[1]) % 2019

for i in range (a[0], a[1]):
  for j in range (i+1, a[1]+1):
    if (i*j)%2019 < b:
      b = (i*j)%2019
      
print(b)      

### FIXED CODE ###

a = [ int(i) for i in input().split()]

b = (a[0]*a[1]) % 2019

for i in range (a[0], a[1]):
  for j in range (i+1, a[1]+1):
    b = min (b, (i*j)%2019)
    
    if b == 0:
      break
      
  if b == 0:
    break
    
print(b)
### BUGGY CODE ###


n = int(raw_input())
stack = []
for i in range(n):
	i = raw_input()
	if "insert" in i:
		stack.insert(0, int(i[7:]))
	elif "delete " in i:
		if int(i[7:]) in stack:
		    stack.remove(int(i[7:]))
	elif "deleteFirst" in i:
		stack.pop(0)
	elif "deleteLast" in i:
		stack.pop()
print " ".join(map(str, stack))

### FIXED CODE ###

from collections import deque
n = int(raw_input())
stack = deque()
for i in range(n):
	i = raw_input()
	if "insert" in i:
		stack.appendleft(int(i[7:]))
	elif "delete " in i:
		if int(i[7:]) in stack:
		    stack.remove(int(i[7:]))
	elif "deleteFirst" in i:
		stack.popleft()
	elif "deleteLast" in i:
		stack.pop()
print " ".join(map(str, stack))
### BUGGY CODE ###

import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret *= 3

memo = np.full(((n+1), (n * max(aa) + 1)), -1, dtype=np.int64)
def dfs0(i, c):
    if 0 <= memo[i, c]:
        return memo[i, c]

    if i == len(aa):
        memo[i, c] = 3 if total <= (2 * c) else 0
        return memo[i][c]

    acc = 0
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c + aa[i])) % 998244353
    memo[i, c] = acc
    return memo[i, c]

def dfs1(i, c):
    if 0 <= memo[i, c]:
        return memo[i, c]

    if i == len(aa):
        memo[i, c] = 3 if total == (2 * c) else 0
        return memo[i, c]

    acc = 0
    acc = (acc + dfs1(i + 1, c)) % 998244353
    acc = (acc + dfs1(i + 1, c + aa[i])) % 998244353
    memo[i, c] = acc
    return memo[i, c]

ret = (ret - dfs0(0, 0)) % 998244353
memo.fill(-1)
ret = (ret + dfs1(0, 0)) % 998244353
print(ret)

### FIXED CODE ###

import sys

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret *= 3


L = (n * max(aa) + 1)
memo = [-1] * ((n+1) * L * 2)
def dfs(i, c):
    key = (i * L * 2) + 2 * c
    if 0 <= memo[key]:
        return memo[key: key+2]

    if i == n:
        memo[key + 0] = 3 if total <= (2 * c) else 0
        memo[key + 1] = 3 if total == (2 * c) else 0
        return memo[key: key + 2]

    v0 = dfs(i + 1, c)
    v1 = dfs(i + 1, c + aa[i])

    memo[key + 0] = (2 * v0[0] + v1[0]) % 998244353
    memo[key + 1] = (v0[1] + v1[1]) % 998244353
    return memo[key: key + 2]

a, b = dfs(0, 0)
ret = (ret - a + b) % 998244353
print(ret)
### BUGGY CODE ###

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

def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    tmp=[0]*(n+1)
    ans=1
    n+=n//2
    n*=2
    while n:
        x=w.pop()
        if x==0:
            ans+=1
            n-=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if tmp[j]==0 or tmp[j]%3!=ans%3:
                    w.appendleft(j)
                    tmp[j]=ans
        if ans%3==0 and tmp[t]==ans:
            print(ans//3)
            exit()
    print(-1)
 
if __name__=="__main__":
    sol()

### FIXED CODE ###

from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    #tmp=[0]*(n+1)
    tmp=[[0,0,0] for i in range(n+1)]
    ans=1
    n+=n//2
    n*=2
    while n:
        x=w.pop()
        if x==0:
            ans+=1
            n-=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if ans%3==0 and j==t:
                    print(ans//3)
                    exit()
                if tmp[j][ans%3]==0:
                    w.appendleft(j)
                    tmp[j][ans%3]=1
    print(-1)

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

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

for i in range(n-1):
    for j in range(n-1-i):
        if A[j] > A[j+1]:
            A[j],A[j+1] = A[j+1],A[j]


max_d = 0
max_index = 0
for i in range(n-1):
    if A[i+1] - A[i] > max_d:
        max_d = A[i+1]-A[i]
        max_index = i

if k-A[n-1]+A[0] > max_d:
    max_d = k-A[n-1]+A[0]
    max_index = n-1

min_distance = 0

if(max_index != n-1):
    min_distance = A[max_index]+k-A[max_index+1]
else:
    min_distance = A[n-1]-A[0]

print(min_distance)


### FIXED CODE ###

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


max_d = 0
max_index = 0
for i in range(n-1):
    if A[i+1] - A[i] > max_d:
        max_d = A[i+1]-A[i]
        max_index = i

if k-A[n-1]+A[0] > max_d:
    max_d = k-A[n-1]+A[0]
    max_index = n-1

min_distance = 0

if(max_index != n-1):
    min_distance = A[max_index]+k-A[max_index+1]
else:
    min_distance = A[n-1]-A[0]

print(min_distance)
### BUGGY CODE ###

n,k = (int(x) for x in input().split())
h = list(int(x) for x in input().split())
dp = []

# i番目までの必要な体力を求める
i = 0
while i != n:

    #i = 0の時
    if i == 0:
        dp.append(0)
        i += 1
        continue

    # i = 1の時
    if i == 1:
        dp.append(abs(h[i] - h[i-1]))
        i += 1
        continue

    # i >= 2の時
    # jの値の設定
    if i - k > 0:
        j = i - k
    else:
        j = 0

    hp = pow(10,18) 
    while j < i:
        
        hp1 = dp[j] + abs(h[i] - h[j])
        
        # 最小の体力を求める
        if hp > hp1:
            hp = hp1

        j += 1

    # 体力の追加
    dp.append(hp)

    i += 1

print(dp[-1])
                  



### FIXED CODE ###

def main():
    n,k = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0]*n
    dp[1] = abs(h[1] - h[0])
    for i in range(2,n):
        dp[i] = min(abs(h[i] - h[j]) + dp[j] for j in range(max(0,i-k),i))
    print(dp[-1])

main()
### BUGGY CODE ###

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
maze=[list(input()) for _ in range(h)]

sy-=1
sx-=1
gy-=1
gx-=1

maze[sy][sx]="S"

dis=[[-1]*w for _ in range(h)]

from collections import deque

dis[sy][sx]=0

def pri(x):
    for item in x:
        print(item)

d = deque([(sx,sy)])
while len(d)>0:
    (x,y)=d.popleft()
    if x==gx and y==gy:
        print(dis[gy][gx])
        maze[gy][gx]="G"

        #pri(dis)
        #pri(maze)

        exit()

    for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
        #print(mx,my,d)
        for j in range(1,k+1):
            nx=x+mx*j
            ny=y+my*j
            #print(y,x,">>",ny,nx)
            if 0<=nx<w and 0<=ny<h:
                if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                    dis[ny][nx]=dis[y][x]+1
                    d.append((nx,ny))
                    #pri(dis)
                else:
                    break
            else:
                break

print(-1)
    


                










### FIXED CODE ###

def main():
    import sys
    from collections import deque
    input=sys.stdin.readline

    h,w,k=map(int,input().split())
    sy,sx,gy,gx=map(int,input().split())

    #maze=[]
    #for _ in range(h):
    #    maze.append(tuple(input()))

    maze=[tuple(input()) for _ in range(h)]

    sy-=1
    sx-=1
    gy-=1
    gx-=1

    #maze[sy][sx]="S"

    dis=[[-1]*w for _ in range(h)]



    dis[sy][sx]=0



    d = deque([(sx,sy)])
    while len(d)>0:
        (x,y)=d.popleft()
        if x==gx and y==gy:
            print(dis[gy][gx])
            #maze[gy][gx]="G"

            #pri(dis)
            #pri(maze)

            exit()

        for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
            #print(mx,my,d)
            for j in range(1,k+1):
                nx=x+mx*j
                ny=y+my*j
                #print(y,x,">>",ny,nx)
                if 0<=nx<w and 0<=ny<h:
                    if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                        if dis[ny][nx]==-1:
                            d.append((nx,ny))
                        dis[ny][nx]=dis[y][x]+1
                        
                        #pri(dis)
                    else:
                        break
                else:
                    break

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

# B
N, K = map(int, input().split())
a_list = list(map(int, input().split()))
NN = N*(N+1) // 2

arr = [0] * NN
res = 0

# bruce
ind = 0
for i in range(N):
    r = 0
    for j in range(i, N):
        r += a_list[j]
        arr[ind] = r
        ind += 1
        
# get Greedy
for m in range(40, 0, -1):
    cnt = 0
    for i in range(NN):
        if (arr[i] // (2**m)) % 2 == 1:
            cnt += 1
    if cnt >= K:
        res += 2**m
        for i in range(NN):
            if (arr[i] // (2**m)) % 2 == 0:
                arr[i] = 0

print(res)

### FIXED CODE ###

# B
N, K = map(int, input().split())
a_list = list(map(int, input().split()))
NN = N*(N+1) // 2

arr = [0] * NN
res = 0

# bruce
ind = 0
for i in range(N):
    r = 0
    for j in range(i, N):
        r += a_list[j]
        arr[ind] = r
        ind += 1
        
# get Greedy
for m in range(40, -1, -1):
    cnt = 0
    for i in range(NN):
        if (arr[i] // (2**m)) % 2 == 1:
            cnt += 1
    if cnt >= K:
        res += 2**m
        for i in range(NN):
            if (arr[i] // (2**m)) % 2 == 0:
                arr[i] = 0

print(res)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]

#正答数のカウント
correct = []
for i in range(N):
    correct.append(A.count(i+1))
hp = Q - K
for i in range(N):
    if correct[i] > hp:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
correct = [0] * N

for a in A:
    correct[a-1] += 1

hp = Q - K
for i in range(N):
    if correct[i] > hp:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import math
h,n=list(map(int,input().split()))
#a=list(map(int,input().split()))
ma=[]
for _ in range(n):
    tmp=list(map(int,input().split()))
    ma.append(tmp)
ma=sorted(ma,key=lambda x:x[1])
ma.reverse()
dp=[[float("inf") for _ in range(h+1)] for _ in range(n)]
for i in range(n):
    dp[i][0]=0
for i in range(1,h+1):
    dp[0][i]=math.ceil(i/ma[0][0])*ma[0][1]
#print(np.array(ma))
for i in range(1,n):
    #print("number:{},magic:{}".format(i,ma[i]))
    for j in range(1,h+1):
        if j<ma[i][0]:
            cal=ma[i][1]
        else:
            #print("sansyo before")
            cal=ma[i][1]+dp[i][j-ma[i][0]]
        #print("j:{},cal:{}".format(j,cal))
        dp[i][j]=min(dp[i-1][j],cal)
    #print()


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


### FIXED CODE ###

import math
#import numpy as np
#"""
h,n=list(map(int,input().split()))
#a=list(map(int,input().split()))


#"""
dp=[[float("inf") for _ in range(h+1)] for _ in range(n)]
dp[0][0]=0
ma=list(map(int,input().split()))
for i in range(1,h+1):
    dp[0][i]=math.ceil(i/ma[0])*ma[1]
#print(np.array(ma))
for i in range(1,n):
    ma=list(map(int,input().split()))
    #print("number:{},magic:{}".format(i,ma[i]))
    for j in range(h+1):
        if j<ma[0]:
            cal=ma[1]
        else:
            #print("sansyo before")
            cal=ma[1]+dp[i][j-ma[0]]
        #print("j:{},cal:{}".format(j,cal))
        dp[i][j]=min(dp[i-1][j],cal)
    #print()


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

N=int(input())
A=list(map(int, input().split()))
A=sorted([(a,p) for p, a in enumerate(A)])[::-1]

dp=[[0]*(N+1) for _ in range(N+1)]
for i,(a,p) in enumerate(A):
  for j in range(i+1):
    #左詰
    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+(p-j)*a)
    #右詰
    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+((N-1-(i-j))-p)*a)
print(max(dp[-1]))

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
A=sorted([(a,p) for p, a in enumerate(A)])[::-1]

dp=[[0]*(N+1) for _ in range(N+1)]
for i,(a,p) in enumerate(A):
  for j in range(i+1):
    #左詰
    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+(p-j)*a)
    #右詰
    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+((N-1-(i-j))-p)*a)
print(max(dp[-1]))
### BUGGY CODE ###

def run():
    r,c,k = map(int,input().split())
    t = [[0 for i in range(c)] for i in range(r)]
    for i in range(k):
        a,b,z = map(int,input().split())
        t[a-1][b-1] = z
    dp = [[[0 for i in range(c)]for i in range(r)]for i in range(4)]
    dp[0][0][0] = 0
    dp[1][0][0] = t[0][0]
    dp[2][0][0] = t[0][0]
    dp[3][0][0] = t[0][0]
    for i in range(r-1):
        dp[0][i+1][0] = dp[1][i][0]
        for j in range(1,4):
            dp[j][i+1][0] = dp[1][i][0]+t[i+1][0]
    for i in range(c-1):
        dp[0][0][i+1] = 0
        for j in range(1,4):
            dp[j][0][i+1] = max(dp[1][0][i],t[0][i+1])
        for j in range(2,4):
            dp[j][0][i+1] = max(dp[2][0][i],dp[1][0][i]+t[0][i+1])
        dp[3][0][i+1] = max(dp[3][0][i],dp[2][0][i]+t[0][i+1])
    for i in range(r-1):
        for j in range(c-1):
            for s in range(0,4):
                dp[s][i+1][j+1] =  max(dp[0][i+1][j],dp[3][i][j+1])
            for s in range(1,4):
                dp[s][i+1][j+1] = max(dp[0][i+1][j]+t[i+1][j+1],dp[1][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            for s in range(2,4):
                dp[s][i+1][j+1] = max(dp[1][i+1][j]+t[i+1][j+1],dp[2][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            dp[3][i+1][j+1] = max(dp[2][i+1][j]+t[i+1][j+1],dp[3][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
    print(dp[3][r-1][c-1])

if __name__ == "__main__":
    run()

### FIXED CODE ###

def run():
    # sys.stdin.readline()
    import sys
    input = sys.stdin.readline
    r,c,k = map(int,input().split())
    t = [[0 for i in range(c)] for i in range(r)]
    for i in range(k):
        a,b,z = map(int,input().split())
        t[a-1][b-1] = z
    t = tuple(t)
    dp = [[[0 for i in range(c)]for i in range(r)]for i in range(4)]
    dp[0][0][0] = 0
    dp[1][0][0] = t[0][0]
    dp[2][0][0] = t[0][0]
    dp[3][0][0] = t[0][0]
    for i in range(r-1):
        dp[0][i+1][0] = dp[1][i][0]
        for j in range(1,4):
            dp[j][i+1][0] = dp[1][i][0]+t[i+1][0]
    for i in range(c-1):
        dp[0][0][i+1] = 0
        for j in range(1,4):
            dp[j][0][i+1] = max(dp[1][0][i],t[0][i+1])
        for j in range(2,4):
            dp[j][0][i+1] = max(dp[2][0][i],dp[1][0][i]+t[0][i+1])
        dp[3][0][i+1] = max(dp[3][0][i],dp[2][0][i]+t[0][i+1])
    for i in range(r-1):
        for j in range(c-1):
            u = max(dp[0][i+1][j],dp[3][i][j+1])
            for s in range(0,4):
                dp[s][i+1][j+1] =  u
            u = max(dp[0][i+1][j]+t[i+1][j+1],dp[1][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            for s in range(1,4):
                dp[s][i+1][j+1] = u
            u = max(dp[1][i+1][j]+t[i+1][j+1],dp[2][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            for s in range(2,4):
                dp[s][i+1][j+1] = u
            dp[3][i+1][j+1] = max(dp[2][i+1][j]+t[i+1][j+1],dp[3][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
    print(dp[3][r-1][c-1])

if __name__ == "__main__":
    run()