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

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


if __name__ == '__main__':
    S = input()

    que = queue.Queue()
    que.put("")
    ans = False
    while not que.empty():
        t = que.get()
        if len(S) == len(t):
            if S == t:
                ans = True
                break
        elif len(S) > len(t):
            if S[:len(t)] == t:
                que.put(t + "dreamer")
                que.put(t + "dream")
                que.put(t + "erase")
                que.put(t + "eraser")

    if ans:
        print("YES")
    else:
        print("NO")


### FIXED CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


if __name__ == '__main__':
    S = input()

    i = 0
    ans = False
    while True:
        res = S[i:i + 5]
        if res == "dream":
            i = i + 5
            if S[i:i + 5] == "dream":
                continue
            elif S[i:i + 7] == "erdream":
                i = i + 2
                continue
            elif S[i:i + 5] == "erase":
                continue
            elif S[i:i + 7] == "ererase":
                i = i + 2
                continue
            elif i == len(S):
                ans = True
                break
            elif i == len(S) - 2:
                if S[i:] == "er":
                    ans = True
                    break
                else:
                    ans = False
                    break
            else:
                ans = False
                break
        elif res == "erase":
            i = i + 5
            if S[i:i + 5] == "dream":
                continue
            elif S[i:i + 6] == "rdream":
                i = i + 1
                continue
            elif S[i:i + 5] == "erase":
                continue
            elif S[i:i + 6] == "rerase":
                i = i + 1
                continue
            elif i == len(S):
                ans = True
                break
            elif i == len(S) - 1:
                if S[i:] == "r":
                    ans = True
                    break
                else:
                    ans = False
                    break
            else:
                ans = False
                break

    if ans:
        print("YES")
    else:
        print("NO")
### BUGGY CODE ###

inp = lambda cast=int: list(map(cast, input().split()))
printf = lambda s='', *args, **kwargs: print(str(s).format(*args), flush=True, **kwargs)
n, = inp()
A = [0.0] + inp(float)
dp = [[0.0 for _ in range(n + 1)] for _ in range(n + 1)]
res = 0.0
for i in range(n + 1):
    for j in range(n + 1):
        if i == 0:
            dp[i][j] = 1 if j == 0 else 0
        elif j == 0:
            dp[i][j] = dp[i-1][j] * (1 - A[i])
        else:
            dp[i][j] = dp[i-1][j] * (1 - A[i]) \
                       + dp[i-1][j-1] * A[i]
        if i == n and j > n/2:
            res += dp[i][j]
printf(res)

### FIXED CODE ###

inp = lambda cast=int: list(map(cast, input().split()))
# printf = lambda s='', *args, **kwargs: print(str(s).format(*args), flush=True, **kwargs)
n, = inp()
A = [0.0] + inp(float)
dp = [[0.0 for _ in range(n + 1)] for _ in range(n + 1)]
res = 0.0
for i in range(n + 1):
    for j in range(n + 1):
        if i == 0:
            dp[i][j] = 1 if j == 0 else 0
        elif j == 0:
            dp[i][j] = dp[i-1][j] * (1 - A[i])
        else:
            dp[i][j] = dp[i-1][j] * (1 - A[i]) \
                       + dp[i-1][j-1] * A[i]
        if i == n and j > n/2:
            res += dp[i][j]
print(res)
### BUGGY CODE ###

N,x = map(int,input().split())
*A, = map(int,input().split())
c = [A[:] for _ in [0]*(N)]
ans = sum(A)
for i in range(1,N):
    for j in range(N):
        c[i][j] = min(c[i-1][j-1],c[i][j])
    ans = min(ans,sum(c[i])+x*i)
print(ans)

### FIXED CODE ###

N,x = map(int,input().split())
*A, = map(int,input().split())
c = [A[:] for _ in [0]*(N)]
ans = sum(A)
for i in range(1,N):
    for j in range(N):
        c[i][j] = min(c[i-1][j-1],c[i][j])
    ans = min(ans,sum(c[i])+x*i)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans, cnt = 0, 0
b = True

while b:
    cnt = 0
    for i in range(len(a)):
        if cnt == 0:
            if a[i] % 2 == 0:
                a[i] = a[i] // 2
                cnt = 1
            else:
                a[i] = a[i] * 3
        else:
            a[i] = a[i] * 3
    if cnt == 1:
        ans += 1
    else:
        b = False
print(ans)


### FIXED CODE ###

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

for i in a:
    while i % 2 == 0:
        i //= 2
        ans += 1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = [int(_) for _ in input().split()]
ans = 0
tmp = 0

for i in range(40, -1, -1):
    onenum = 0
    for j in A:
        if 2**i & j == 2**i:
            onenum += 1
    
    zeronum = N - onenum
    
    if tmp + 2**i > K:
        ans += onenum * 2**i
    else:
        if onenum > zeronum:
            ans += onenum * 2**i
        else:
            ans += zeronum * 2**i
            tmp += 2**i

print(ans)

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
MAX_DIGIT = 50
A = [int(_) for _ in input().split()]
dp = np.full((MAX_DIGIT+1, 2), -1, dtype=np.int64)
dp[0][0] = 0

for d in range(MAX_DIGIT):
    mask = 1 << (MAX_DIGIT - 1 - d)
    onenum = 0
    for i in A:
        if (i & mask) == mask:
            onenum += 1
    
    cost0 = mask * onenum
    cost1 = mask * (N - onenum)
    
    if dp[d][1] != -1:
        dp[d+1][1] = max(dp[d+1][1], dp[d][1] + max(cost0, cost1))
    
    if dp[d][0] != -1:
        if K & mask:
            dp[d+1][1] = max(dp[d+1][1], dp[d][0] + cost0)
    
    if dp[d][0] != -1:
        if K & mask:
            dp[d+1][0] = max(dp[d+1][0], dp[d][0] + cost1)
        else:
            dp[d+1][0] = max(dp[d+1][0], dp[d][0] + cost0)

print(max(dp[MAX_DIGIT][0], dp[MAX_DIGIT][1]))
### BUGGY CODE ###

b = int(input())
a = [i for i in range(b)]
if b % 2 == 1:
    print((b-1) * ((b-1) // 2) + ((b-1) // 2))
else:
    print((b - 1) * ((b-1) // 2 + 1))

### FIXED CODE ###

b = int(input())
if b % 2 == 1:
    print((b-1) * ((b-1) // 2) + ((b-1) // 2))
else:
    print((b - 1) * ((b-1) // 2 + 1))
### BUGGY CODE ###

# 入力
N = int(input())
An = [int(x) for x in input().split()]
 
# 組み合わせ
L = [0]
for i in range(0,N+1):
    L.append(int(i*(i+1)/2))

# 各数字の個数を求める
Cn = [An.count(i) for i in range(1,N+1)]
 
# 全部の組み合わせ
Dn = [L[Cn[i-1]] for i in range(1,N+1)]
s = sum(Dn)

for i in range(1,N+1):
    print(s - (Cn[An[i-1]-1] - 1))

### FIXED CODE ###

import collections as c

# 入力
N = int(input())
An = [int(x) for x in input().split()]
 
# 各数字の個数を求める
Cn = c.Counter(An)
 
# 全部の組み合わせ
s = 0
for v in Cn.values():
    s += int(v*(v-1) / 2)

for i in range(0,N):
    print(s - (Cn[An[i]] - 1))
### BUGGY CODE ###

def main():
    n = int(input())
    s = input()

    ans = 0
    for i in range(1, n):
        cnt = 0
        for j in range(n-i):
            if s[i+j] == s[j]:
                cnt += 1
            else:
                ans = max(ans, min(cnt, i))
                cnt = 0
        ans = max(ans, min(cnt, i))

    print(ans)

main()


### FIXED CODE ###

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

n += 1
s += "#"

ans = 0
for i in range(1, n):
    cnt = 0
    for j in range(n-i):
        if s[i+j] == s[j]:
            cnt += 1
        else:
            ans = max(ans, min(cnt, i))
            cnt = 0

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

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

total = []
Y = []

for i in range(N):
	if i == N-1:
		Y = Y + [S[i]]
		break
	if S[i] == S[i+1]:
		continue
	else:
		Y = Y + [S[i]]
		
print(len(Y)) 

### FIXED CODE ###

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

total = []
Y = 0

for i in range(N):
	if i == N-1:
		Y = Y + 1
		break
	if S[i] == S[i+1]:
		continue
	else:
		Y = Y + 1
		
print(Y)
### BUGGY CODE ###

S=input()
rev=False
for _ in range(int(input())):
    l = input().split()
    if len(l)==1:
        rev = not rev
    else:
        if rev^(l[1]=="1"):
            S=l[2]+S
        else:
            S+=l[2]
print(S[::1*(-1 if rev else 1)])
        


### FIXED CODE ###

S=input()
Q=int(input())
head=""
tail=""
rev=False

for _ in range(Q):
    q = input().split()
    if len(q)==1:
        rev = not rev
    else:
        if rev ^ (q[1]=="1"):
            head+=q[2]
        else:
            tail+=q[2]
if rev:
    print(tail[::-1]+S[::-1]+head)
else:
    print(head[::-1]+S+tail)
### BUGGY CODE ###

K, S = map(int, input().split())
count = 0
for i in range(S + 1):
    X = S - i
    for j in range(i + 1):
        Y = j
        Z = S - X - Y
        if K >= X >= 0 and K >= Y >= 0 and K >= Z >= 0:
            count += 1
print(count)


### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for i in range(K + 1):
    for j in range(K + 1):
        Z = S - i - j
        if K >= Z >= 0:
            count += 1
print(count)
### BUGGY CODE ###

N,X,D=map(int,input().split())
f,c,r={},[0]*8**9,0
for x,y,z in sorted((((N-k)*j+~-k)*k//2+k*X//D,j,k*X%D) if D else(0,j,k*(X!=0))for k in range(N+1)for j in[0,2]):
 if c[z]+y<1:
  f[z]=x
 r+=(x-f[z]+1)*(c[z]<y)
 c[z]-=y-1
print(r)

### FIXED CODE ###

N, X, D = map(int, input().split())
if D == 0:
    r = N+1
    if X == 0:
        r = 1
    print(r)
else:
    if D < 0:
        X, D = -X, -D
    d = dict()
    for k in range(N+1):
        M = (k*X) % D
        F = (k*X)//D + ((k-1)*k)//2 #(1..k-1)
        L = (k*X)//D + (2*N-k-1)*k//2# (N-k..N-1)
        if M not in d:
            d[M] = list()
        d[M].append((F, 0))
        d[M].append((L, 1))
    r = 0
    for m in d:
        d[m] = sorted(d[m])
        fc = 0
        f = 0
        for x in d[m]:
            if not x[1]:
                fc += 1
                if fc == 1:
                    f = x[0]
            if x[1]:
                fc -= 1
                if fc == 0:
                    r += x[0] - f + 1
    print(r)
### BUGGY CODE ###

def scheduler(N, A):
    days = 0
    while True:
        games = []
        no_player = True
        for i in range(N):
            if len(A[i]):
                no_player = False
                oppo = A[i][-1] -1
                if A[oppo][-1] - 1 == i:
                    games.append(i)
        if no_player:
            break
        days += 1
        if len(games) == 0:
            return(-1)
        for game in games:
            A[game].pop()
    return(days)

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

print(scheduler(N, A))

### FIXED CODE ###

def list_up_next_games(players):
    games = set()
    for p in players:
        if A[p]:
            opponent = A[p][-1] - 1
            if A[opponent][-1] - 1 == p:
                if p < opponent:
                    games.add((p, opponent))
                else:
                    games.add((opponent, p))
    return(games)

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

games = list_up_next_games(list(range(N)))

done_games = []
days = 0
while games:
    days += 1
    players = []
    for game in games:
        done_games.append(game)
        A[game[0]].pop()
        A[game[1]].pop()
        players.append(game[0])
        players.append(game[1])
    games = list_up_next_games(players)

if len(done_games) == N*(N-1)//2:
    print(days)
else:
    print(-1)
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
ans = A[0]

if 0 in A:
    print(0)
    exit()

for i in range(1, len(A)):
    ans *= A[i]
    if A[i] > 10**18:
        print(-1)
        exit()

if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import numpy as np
N = int(input())
A = [int(a) for a in input().split()]
ans = A[0]

if 0 in A:
    print(0)
    exit()

for i in range(1, len(A)):
    if A[i] != 1:
        ans *= A[i]
    if ans > 10**18:
        print(-1)
        exit()

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

n=int(input())
h=list(map(int,input().split()))
h.append(float('inf'))
ans=0
cnt=0
for i in range(n):
  c=h[i]
  for j in range(i+1,n+1):
    if c>=h[j]:
      cnt+=1
      c=h[j]
    else:
      ans=max(ans,cnt)
      cnt=0
      break
print(ans)

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
h.append(float('inf'))
ans=0
cnt=0
for i in range(n):
  if h[i]>=h[i+1]:
      cnt+=1
  else:
    ans=max(ans,cnt)
    cnt=0
ans=max(ans,cnt)
print(ans)
### BUGGY CODE ###

INF = 10**15
hp, n_magic = map(int, input().split())
magic_data = tuple(tuple(map(int, input().split())) for _ in range(n_magic))
hp_gauge = [0] + [INF] * hp

for i in range(hp):
    for j in range(len(magic_data)):
        damage_total = i + magic_data[j][0]
        if damage_total > hp:
            damage_total = hp
        hp_gauge[damage_total] = min(hp_gauge[damage_total], hp_gauge[i] + magic_data[j][1])

print(hp_gauge[hp])

### FIXED CODE ###

import numpy as np
max_hp, n_magic = map(int, input().split())
power = np.empty(n_magic, dtype='int')
mp = np.empty(n_magic, dtype='int')
for i in range(n_magic):
    power[i], mp[i] = map(int, input().split())

hp_gauge = np.array([float('inf')] * (max_hp+1))
hp_gauge[0] = 0

for remaining_hp in range(1, max_hp+1):
    pre_turn_hp = remaining_hp - power
    pre_turn_hp[pre_turn_hp < 0] = 0
    hp_gauge[remaining_hp] = np.min(hp_gauge[pre_turn_hp] + mp)
    
print(int(hp_gauge[max_hp]))
### BUGGY CODE ###

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):
    l=[]
    for j in range(max(0,i-k),i):
        l.append(dp[j]+abs(h[i]-h[j]))
    dp[i]=min(l)
    #print(l)
print(dp[-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline
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):
    l=[]
    for j in range(max(0,i-k),i):
        l.append(dp[j]+abs(h[i]-h[j]))
    dp[i]=min(l)
    #print(l)
print(dp[-1])
### BUGGY CODE ###

N = int(input())
count = 0
def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return len(table) 
for X in range(1,N):
  count += divisor(X)
print(count)
  
  

### FIXED CODE ###

N = int(input())
ans = 0
for A in range(1,N):
  ans += (N-1) // A
print(ans)
### BUGGY CODE ###

def t(n, k, q, a):
    for i in range(n):
        print("Yes" if (-q + k + a.count(i + 1)) > 0 else "No")

if __name__ == "__main__":
    n, k, q = map(int, input().split())
    a = [int(input()) for i in range(q)]
    r = t(n, k, q, a)


### FIXED CODE ###

def t(n, k, q, a):
    p = [-q + k] * n
    for i in range(q):
        p[a[i-1]-1] += 1
    return ["Yes" if i > 0 else "No" for i in p]
   

if __name__ == "__main__":
    n, k, q = map(int, input().split())
    a = [int(input()) for i in range(q)]
    r = t(n, k, q, a)
    for i in r:
        print(i)
### BUGGY CODE ###

#!/usr/bin/python3

import sys
import resource
import bisect
from collections import defaultdict

sys.setrecursionlimit(1000000)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))


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

nbs = defaultdict(list)

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    ca = a[cur]

    oidx = 0
    ov = 0
    
    idx = bisect.bisect_left(dp, ca)
    ov = dp[idx]

    ntail = ctail
    if ctail < idx:
        ntail = idx

    dp[idx] = ca
    mlen[cur] = ntail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ntail)

    dp[idx] = ov
    return



mlen[0] = 1
dp[0] = a[0]
for ch in nbs[0]:
    getmlen(ch, 0, 0)

for i in range(n):
    print(mlen[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left
 
N = int(input())
a = [int(i) for i in input().split()]
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  u, v = map(int, input().split())
  vec[u - 1].append(v - 1)
  vec[v - 1].append(u - 1)
 
lis = [a[0]]
ret = [0] * N
def dfs(cur, pre) :
  for nex in vec[cur] :
    if nex == pre : continue
    if a[nex] > lis[-1] :
      lis.append(a[nex])
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis.pop()
    else :
      pos = bisect_left(lis, a[nex])
      v = lis[pos]
      lis[pos] = a[nex]
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis[pos] = v
 
dfs(0, -1)
 
ret[0] = 1
for i in range(N) :
  print(ret[i])
### BUGGY CODE ###

def main():
    MOD = 10 ** 9 + 7

    N = int(input())
    *a, = map(int, input().split())

    b = [0] * 60
    for x in a:
        for j in range(60):
            b[j] += (x & 1) > 0
            x >>= 1

    t = 1
    ans = 0
    for j in range(60):
        ans = (ans + b[j] * (N - b[j]) * t) % MOD
        t <<= 1
    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


### FIXED CODE ###

def main():
    import sys

    input = sys.stdin.readline

    mod = 10 ** 9 + 7
    n = int(input())
    a = tuple(map(int, input().split()))

    b = [0] * 60

    for j in range(60):
        for x in a:
            if (x >> j) & 1:
                b[j] += 1

    ret = 0
    for j in range(60):
        ret = (ret + b[j] * (n - b[j]) * (1 << j)) % mod

    print(ret)


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

import sys
import fractions
input = sys.stdin.readline



def main():
    N = int(input())
    a = [int(i) for i in input().split()] 
    M = 10**9+7
    ans = a[0]
    total = 0
    for i in range(1, N):
        ans = ans * a[i] // fractions.gcd(ans, a[i])

    for j in range(N):
        total += ans//a[j]
        total %= M

    print(int(total))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline


def gcd(x, y):
    while y > 0:
        r = x%y
        x = y
        y = r
    return x
 
def lcm(x, y):
    return x//fractions.gcd(x, y)*y
 
n = int(input())
a = list(map(int, input().split()))
 
l = 1
for x in a:
    l = lcm(x, l)
 
ans = 0
for x in a:
    ans += l//x
 
print(ans%(10**9+7))
### BUGGY CODE ###

n=int(input())
h=list(map(int,input().split()))
a=True
for i in range(n):
  for j in range(i,n):
    if h[i]-h[j]>1:
      a=False
      break
if a==False:
  print('No')
else:
  print('Yes')

### FIXED CODE ###

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

for i in range(n-1):
  if h[i]<h[i+1]:
    h[i+1]-=1
if sorted(h)==h:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

N, K = map(int, input().split())
exps = [
    float(sum(range(1, p + 1))) / float(p)
    for p in map(int, input().split())
]
ans = 0
for i in range(N - K + 1):
    exp = sum([e for e in exps[i:i+K]])
    if ans < exp:
        ans = exp
print(ans)

### FIXED CODE ###

from math import fsum
s = [0] * 1001
for i in range(1, len(s)):
    s[i] = s[i - 1] + i
N, K = map(int, input().split())
exps = [s[p] / p for p in map(int, input().split())]
exp = fsum(exps[:K])
ans = exp
for i in range(K, N):
    exp = fsum((exp, -exps[i - K], exps[i]))
    if ans < exp:
        ans = exp
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)

memo={}
def c(n,k):
    if (n,k) in memo:
        return memo[(n,k)]
    else:
        memo[(n,k)] = 1 if(k<=0 or n<=k) else ( c(n-1, k-1) + c(n-1, k) ) % 1000000007
    return memo[(n,k)]

n,k=map(int,input().split())
a=sorted(map(int,input().split()))
num=c(n,k)
hoge=[]
while True:
    hoge.append(c(n-1,k-1))
    if n-1==k-1:
        break
    n-=1

ans=0
for i in range(len(hoge)):
    ans-=hoge[i]*a[i]%1000000007
    ans+=hoge[i]*a[-i-1]%1000000007
    ans%=1000000007
print(ans)



### FIXED CODE ###

def modpow(x,p,mod):
    ret=1
    for i in range(64):
        if (1<<i)&p:
            ret=ret*x%mod
        x=x*x%mod
    return ret

def inverse_table(n,mod):
    table=[]
    for i in range(0,n+1):
        table.append(modpow(i,mod-2,mod))
    return table

def factorial_table(n,mod):
    table=[1]
    for i in range(1,n+1):
        table.append(table[-1]*i%mod)
    return table

def inverse_factorial_table(n,it,mod):
    table=[1]
    for i in range(1,n+1):
        table.append(table[-1]*it[i]%mod)
    return table

it=inverse_table(10**5,1000000007)
ft=factorial_table(10**5,1000000007)
ift=inverse_factorial_table(10**5,it,1000000007)
def c(n,k,it,ft,mod):
    return ft[n]*ift[k]*ift[(n-k)]%mod
n,k=map(int,input().split())
a=sorted(map(int,input().split()))
hoge=[]
while True:
    hoge.append(c(n-1,k-1,it,ft,1000000007))
    if n-1==k-1:
        break
    n-=1
ans=0
for i in range(len(hoge)):
    ans-=hoge[i]*a[i]%1000000007
    ans+=hoge[i]*a[-i-1]%1000000007
    ans%=1000000007
print(ans)
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = []

for i in li:
    ans.append(i)
    ans = ans[::-1]

print(*ans)

### FIXED CODE ###

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

if n%2 == 0:
    ans = li[1::2][::-1] + li[::2]
else:
    ans = li[::2][::-1] + li[1::2]

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

import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

def main():
    r,c,k=map(int,input().split())
    rcv=[list(map(int,input().split())) for i in range(k)]

    dpm=[[0]*4 for i in range(c+1)]
    dpn=[[0]*4 for i in range(c+1)]

    dic={}
    for i in range(k):
        r1,c1,v=rcv[i]
        dic[(r1,c1)]=v

    for i in range(r):
        for j in range(c):
            dpn[j+1][0]=max(dpn[j+1][0],max(dpm[j+1]))
            if (i+1,j+1) in dic:
                for k in range(3)[::-1]:
                    dpn[j+1][k+1]=max(dpn[j+1][k]+dic[(i+1,j+1)],dpn[j][k]+dic[(i+1,j+1)])
            for k in range(4):
                dpn[j+1][k]=max(dpn[j+1][k],dpn[j][k])
        # print(dpn)
        dpm=copy.deepcopy(dpn)
        dpn=[[0]*4 for i in range(c+1)]
    print(max(dpm[-1]))

main()

### FIXED CODE ###

import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

def main():
    r,c,k=map(int,input().split())
    rcv=[list(map(int,input().split())) for i in range(k)]

    dpn=[[0]*4 for i in range(c+1)]

    dic={}
    for i in range(k):
        r1,c1,v=rcv[i]
        dic[(r1,c1)]=v

    for i in range(r):
        for j in range(c):
            dpn[j+1][0]=max(dpn[j+1][0],max(dpn[j+1]))
            if (i+1,j+1) in dic:
                for k in range(3)[::-1]:
                    dpn[j+1][k+1]=max(dpn[j+1][k]+dic[(i+1,j+1)],dpn[j][k]+dic[(i+1,j+1)])
            for k in range(4):
                dpn[j+1][k]=max(dpn[j+1][k],dpn[j][k])
        # print(dpn)
    print(max(dpn[-1]))

main()