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

n, m = map(int, input().split())
a = [None]*m
c = [0]*m
for i in range(m):
    a[i], b = map(int, input().split())
    ls = list(map(int,input().split()))
    for j in ls:
        c[i] |= 1<<(j-1)
n2 = 1<<n
dp = [1e9]*(n2)
dp[0] = 0
for i in range(m):
    for S in range(n2):
        dp[S|c[i]] = min(dp[S|c[i]], dp[S]+a[i])
if dp[(n2)-1] < 1e9:
    print(dp[(n2)-1])
else:
    print(-1)

### FIXED CODE ###

n, m = map(int, input().split())
a = [None]*m
c = [0]*m
for i in range(m):
    a[i], b = map(int, input().split())
    ls = list(map(int,input().split()))
    for j in ls:
        c[i] |= 1<<(j-1)

dp = [[1e9]*(1<<n) for i in range(m+1)]
dp[0][0] = 0
for i in range(m):
    for S in range(1<<n):
        dp[i+1][S] = min(dp[i+1][S], dp[i][S])
        dp[i+1][S|c[i]] = min(dp[i+1][S|c[i]], dp[i][S]+a[i])
if dp[m][(1<<n)-1] < 1e9:
    print(dp[m][(1<<n)-1])
else:
    print(-1)
### BUGGY CODE ###

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

for i in range(N):
    ans += a[-2]
    a = a[1:-2]
print(ans)

### FIXED CODE ###

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

a.sort(reverse=True)
ans = 0
count = 0
for i in range(1, N*3+1, 2):
    if count == N:
        break
    else:
        ans += a[i]
        count += 1

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

from operator import mul
from functools import reduce
from collections import Counter
from copy import deepcopy

def main():

    def cmb(n,r):
        r = min(n-r,r)
        if r == 0: return 1
        over = reduce(mul, range(n, n - r, -1))
        under = reduce(mul, range(1,r + 1))
        return over // under

    n = int(input())
    A = [int(x) for x in input().split()]
    a_c= Counter(A)
    cnt = 0
    for a in A:
        a_c_c = deepcopy(a_c)
        a_c_c[a] = a_c_c[a] - 1
        values = a_c_c.values()
        val_cnt = Counter(values)
        cnt = {cmb(k, 2) * v  if k > 1 else 0 for k, v in val_cnt.items()}
        print(sum(cnt))
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter
 
def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    a_c = Counter(A)
    res = [int(v*(v-1)/2) for v in a_c.values()]
    cnt = sum(res)
    for a in A:
        ans = (cnt - (a_c[a]-1))
        print(ans)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
start = []
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            start.append(i*W+k)

for i in start:
    q.append(i)
    saitan[i] = 0
#print(start)
def bfs(h,w,q,Saitan):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] != 1000000:
                #print('b')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan))
#print(saitan)

### FIXED CODE ###

from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            q.append(i*W+k)
            saitan[i*W+k] = 0
len_q = len(q)

#print(start)
def bfs(h,w,q,Saitan,len_Q):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and len_Q < h * w:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            len_Q += 1
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan,len_q))
#print(saitan)
### BUGGY CODE ###

n, k, *p_n = map(int, open(0).read().split())

exp = [0] * (n - k + 1)

for i in range(n - k + 1):
    total = 0
    for j in range(k):
        total += (p_n[i + j] + 1)
        
    exp[i] = total * 0.5
    
print(max(exp))

### FIXED CODE ###

n, k, *p_n = map(int, open(0).read().split())
p_n.insert(0, 0)
for i in range(n):
    p_n[i + 1] = ((p_n[i + 1] + 1) / 2) + p_n[i]

exp_sum = [0] * (n - k + 1)
for i in range(n - k + 1):
    exp_sum[i] = p_n[i + k] - p_n[i]
    
print(max(exp_sum))
### BUGGY CODE ###

#DSL_3-D Sliding Window - Sliding Minimum Elements
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
if N == 10**5 : 
    try :
        count += 1
    except NameError :
        count = 1
for i in range(N-L+1) : ans.append(min(A[i:i+L]))
try :
    count += 1
    if count < 3 :
        for i in ans[:-1] : print(i, end=" ")
        print(ans[-1])
except :
    for i in ans[:-1] : print(i, end=" ")
    print(ans[-1])

    

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

k,s = map(int,input().split())
Xm = k
Ym = k
Zm = k
count = 0
for i in range(Xm+1):
  for j in range(Ym+1):
    for m in range(Zm+1):
      if i+j+m == s:
        count += 1
print(count)

### FIXED CODE ###

k,s = map(int,input().split())
Xm = k
Ym = k
Zm = k #使わない
count = 0
for i in range(Xm+1):
  for j in range(Ym+1):
    if 0<= s - (i+j) <= k:
        count += 1
print(count)
### BUGGY CODE ###

# E
# -*- coding: utf-8 -*-
H, N = map(int, input().split())
A_list = []
B_list = []
for i in range(N):
    A, B = map(int, input().split())
    A_list.append(A)
    B_list.append(B)

dp = [0 for _ in range(H + 1)]
dp[0] = 0
 
for i in range(1, H + 1):
    dp[i] = min([(dp[i - A_list[j]] if i >= A_list[j] else 0) + B_list[j] for j in range(N)])

print(dp[-1])

### FIXED CODE ###

# E
# -*- coding: utf-8 -*-
H, N = map(int, input().split())
A_list = []
B_list = []
for i in range(N):
    A, B = map(int, input().split())
    A_list.append(A)
    B_list.append(B)

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

def test_func(dp, A_list, B_list, i, N):
    return(min([(dp[i - A_list[j]] if i >= A_list[j] else 0) + B_list[j] for j in range(N)]))


for i in range(1, H + 1):
    dp[i] = test_func(dp, A_list, B_list, i, N)

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

from collections import deque

N, K = map(int, input().split())
T = [[] for i in range(N)]
E = []
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    T[a].append(b)
    T[b].append(a)
    E.append([a, b])


def bfs(n):
    visited = [False] * N
    dist = [0] * N
    queue = deque([n])
    while queue:
        node = queue.pop()
        if visited[node]:
            continue
        visited[node] = True
        for n in T[node]:
            if not visited[n]:
                dist[n] = dist[node] + 1
                queue.appendleft(n)
    return dist


dist = []
for i in range(N):
    dist.append(bfs(i))

ans = float('inf')
if K % 2 == 0:
    for i in range(N):
        ans = min(ans, len([d for d in dist[i] if d > K / 2]))

else:
    for a, b in E:
        ans = min(ans, len([d for d in [min(d1, d2) for d1, d2 in zip(dist[a], dist[b])] if d> (K-1) / 2]))

print(ans)


### FIXED CODE ###

from collections import deque

N, K = map(int, input().split())
T = [[] for i in range(N)]
E = []
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    T[a].append(b)
    T[b].append(a)
    E.append((a, b))


def dfs(n):
    visited = [False] * N
    stack = [[n, 0]]
    longest = [-1, -1]

    while stack:
        node, weight = stack.pop()
        if visited[node]:
            continue
        visited[node] = True
        if longest[1] < weight:
            longest = [node, weight]

        for n in T[node]:
            if not visited[n]:
                stack.append([n, weight + 1])

    return longest


def bfs(n):
    visited = [False] * N
    dist = [0] * N
    queue = deque([n])
    while queue:
        node = queue.pop()
        if visited[node]:
            continue
        visited[node] = True
        for n in T[node]:
            if not visited[n]:
                dist[n] = dist[node] + 1
                queue.appendleft(n)
    return dist


xn, xw = dfs(0)
yn, yw = dfs(xn)
diameter = yw

d = bfs(0)
ans = float('inf')
if K % 2 == 0:
    # 全ての頂点について全探索
    for i in range(N):
        dist = bfs(i)
        ans = min(ans, len(list(filter(lambda x: K / 2 < x, dist))))
else:
    # 全ての辺について全探索
    for a, b in E:
        dist1 = bfs(a)
        dist2 = bfs(b)
        dist = [min(d1, d2) for d1, d2 in zip(dist1, dist2)]
        ans = min(ans, len(list(filter(lambda x: (K-1) / 2 < x, dist))))

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

import sys
sys.setrecursionlimit(1000000)

n,m = map(int,input().split())

a_list=[]
for i in range(m):
    a_list.append(int(input()))

def count(now,s,e):
    if now > e:
        return 0
    if now == e:
        return 1
    cnt=0
    cnt+=count(now+1,s,e)
    cnt+=count(now+2,s,e)
    return cnt


c_mod=1000000007
start=0
end=0
ans=1
before=100000
for a in a_list:
    if abs(before-a)==1:
        print(0)
        exit()
    # 各部分の移動方法
    end=a-1
    ans=ans*count(start,start,end)%c_mod
    start=a+1
    before=a
if end<n:
    end=n
    ans=ans*count(start,start,end)%c_mod
print(ans)


### FIXED CODE ###

c_mod=1000000007
n,m = map(int,input().split())

step=[0]*(n+1)
for _ in range(m):
    a=int(input())
    step[a-1]=-1

if step[0]!=-1:
    step[0]=1
if step[1]!=-1:
    step[1]=1
for i in range(n-1):
    if step[i]==-1:
        continue
    if step[i+1]!=-1:
        step[i+1]+=step[i]
    if step[i+2]!=-1:
        step[i+2]+=step[i]
print(step[n-1]%c_mod)
### BUGGY CODE ###


n, m = list(map(lambda x:int(x), input().split()))

key_list = {}

for i in range(m):
    key_price, _ = list(map(lambda x:int(x), input().split()))
    open_list = list(map(lambda x:int(x), input().split()))
    key_list[i] = [key_price, open_list]
    
situation_val = 1 << n

dp = [[float('INF')] * situation_val for i in range(m+1)]
dp[0][0] = 0

for i in range(m):
    price = key_list[i][0]
    treasure = key_list[i][1]
    key_val = 0
    for v in treasure:
        key_val += (1 << v-1)
        
    for j in range(situation_val):
        key_used_situation = j | key_val
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        dp[i+1][key_used_situation] = min(dp[i][key_used_situation], dp[i+1][key_used_situation], dp[i][j]+price)
        
        
ans = dp[m][situation_val-1]

if ans == float('inf'):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n, m = list(map(lambda x:int(x), input().split()))
 
key_list = {}
 
for i in range(m):
    key_price, _ = list(map(lambda x:int(x), input().split()))
    open_list = list(map(lambda x:int(x), input().split()))
    key_list[i] = [key_price, open_list]
    
situation_val = 1 << n
 
dp = [[float('INF')] * situation_val for i in range(m+1)]
for i in range(m+1):
    dp[i][0] = 0
 
for i in range(m):
    price = key_list[i][0]
    treasure = key_list[i][1]
    key_val = 0
    for v in treasure:
        key_val += (1 << v-1)
        
    for j in range(situation_val):
        key_used_situation = j | key_val
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        dp[i+1][key_used_situation] = min(dp[i+1][key_used_situation], dp[i][j]+price)
        
        
ans = dp[m][situation_val-1]

if ans == float('inf'):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0]*N
    for i in range(1,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 ###

if __name__ == '__main__':
    d = input()
    n = int(input())
    for _ in range(n):
        q = input()
        if q[0] == ('1'):
            d = d[::-1]
        elif q[:3] == ("2 1"):
            d = q[-1]+d
        elif q[:3] == ("2 2"):
            d=d+q[-1]
    print(d)

### FIXED CODE ###

if __name__ == '__main__':
    d = input()
    n = int(input())
    qs = [input() for e in range(n)]
    s = []
    e = []
    r = False
    for q in qs:
        if q == '1':
            r = not(r)
        elif q.startswith("2 1"):
            e.append(q[-1]) if r else s.append(q[-1])
        else:
            s.append(q[-1]) if r else e.append(q[-1])
    print("".join(e[::-1]) + d[::-1] + "".join(s) if r else "".join(s[::-1]) + d + "".join(e))
### BUGGY CODE ###

from collections import defaultdict, deque
outs = defaultdict(list)
ins = defaultdict(int)

def get_ab(h):
    return h // 10000, h % 10000

def get_hash(a, b):
    if a >= b:
        return 10000*a + b
    else:
        return 10000*b + a
v = []
N = int(input())
for i in range(N):
    nums = list(map(int, input().split()))
    pred = get_hash(i+1, nums[0])
    v.append(pred)
    for j in range(len(nums)-1):
        now = get_hash(i+1, nums[j+1])
        outs[pred].append(now)
        ins[now] += 1
        pred = now

v = set(v)
q = deque(v1 for v1 in v if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)
if len(res) < (N*(N-1)) // 2:
    print(-1)
else:
    ans = 0
    before = []
    for h in res:
        a, b = get_ab(h)
        if (a in before) or (b in before):
            before = [a, b]
            ans += 1
        else:
            before.append(a)
            before.append(b)
    print(ans+1)


### FIXED CODE ###

from collections import defaultdict, deque
outs = defaultdict(list)
ins = defaultdict(int)

def get_ab(h):
    return h // 10000, h % 10000

def get_hash(a, b):
    if a >= b:
        return 10000*a + b
    else:
        return 10000*b + a
v = []
N = int(input())
for i in range(N):
    nums = list(map(int, input().split()))
    pred = get_hash(i+1, nums[0])
    if pred not in v:
        v.append(pred)
    for j in range(len(nums)-1):
        now = get_hash(i+1, nums[j+1])
        outs[pred].append(now)
        ins[now] += 1
        pred = now

q = deque(v1 for v1 in v if ins[v1] == 0)
res = []
ans = 0
before = []
while q:
    v1 = q.popleft()
    res.append(v1)
    a, b = get_ab(v1)
    if (a in before) or (b in before):
        before = [a, b]
        ans += 1
    else:
        before.append(a)
        before.append(b)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)
if len(res) < (N*(N-1)) // 2:
    print(-1)
else:
    print(ans+1)
### BUGGY CODE ###

n = int(input())
A = input().split()
B = []
for a in A:
    B.append(a)
    B.reverse()
print(' '.join(B))

### FIXED CODE ###

n = int(input())
a = input().split()

if n % 2 != 0:
    r, l = a[1::2], a[::2]
else:
    r, l = a[::2], a[1::2]

l.reverse()
print(' '.join(l + r))
### BUGGY CODE ###

import sys

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

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

    mod = 10 ** 9 + 7
    n = len(S)
    ans = 0

    fact =[1]*(K+n)
    factinv = [1]*(K+n)


    for i in range(2,K+n):
        fact[i] = (fact[i-1] * i) % mod
        factinv[i] = pow(fact[i],mod-2,mod)

    def nCr(n,r):
        return (fact[n] * factinv[r] * factinv[n-r]) % mod

    for i in range(K+1):
        #ans += ((25 ** i * nCr(i+n-1,n-1)) * (26 ** (K - i))) % mod
        ans += ((25 ** i * fact[i+n-1] * factinv[n-1] * factinv[i] ) * (26 ** (K - i))) % mod
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

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

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

    mod = 10 ** 9 + 7
    n = len(S)
    ans = 0

    fact =[1]*(K+n)
    factinv = [1]*(K+n)
    inv = [0,1]


    for i in range(2,K+n):
        fact[i] = (fact[i-1] * i) % mod
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv[i] = (factinv[i-1] * inv[i]) % mod

    def nCr(n,r):
        r = min(r,n-r)
        return (fact[n] * factinv[r] * factinv[n-r]) % mod

    for i in range(K+1):
        tmp = pow(25,i,mod)
        tmp *= nCr(i+n-1,n-1)
        tmp *= pow(26,K-i,mod)
        ans += tmp
        ans %= mod
    print(ans)

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

k, s = map(int, input().split(' '))

count = 0
for x in range(0,k+1):
    for y in range(0, k+1):
        for z in range(0, k+1):
            if x + y + z == s:
                count += 1
                
print(count)

### FIXED CODE ###

k, s = map(int, input().split(' '))

count = 0
for x in range(0,k+1):
    for y in range(0, k+1):
        z = s - (x + y)
        if 0 <= z <= k:
            count +=1
                
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n, k = map(int, raw_input().split())
baggages = []
weight_sum = 0
for i in range(n):
    baggages.append(int(raw_input()))
for i in baggages:
    weight_sum += i
P_min = int(weight_sum/k)
for i in baggages:
    P_min = max(P_min, i)
tmp = P_min
while True:
    flag = True
    trucks = k-1
    i = 0
    while i < n:
        baggage = baggages[i]
        if tmp >= baggage:
            tmp -= baggage
            i += 1
        else:
            tmp = P_min
            if trucks > 0:
                trucks -= 1
            else:
                flag = False
                break
    if flag:
        break
    else:
        P_min += 1
        tmp = P_min
print P_min

### FIXED CODE ###

# -*- coding: utf-8 -*-

def maxStack(k, p, W):
    nw = 0
    count = 0
    t = 1
    for x in W:
        if x > p:
            return count
        if nw + x <= p:
            nw += x
            count += 1
        else:
            if t == k:
                return count
            else:
                t += 1
                nw = x
                count += 1
    return count

n, k = map(int, raw_input().split())
W = [int(raw_input()) for i in range(n)]
left = 1
right = sum(W)
while left < right:
    mid = (left+right)/2
    v = maxStack(k, mid, W)
    if v >= n:
        right = mid
    else:
        left = mid+1
print left
### BUGGY CODE ###

S = input()

count = 0
for j in range(4, len(S)+1):
    for i in range(len(S)-j+1):
        #print(int(S[i:i+j]))
        if int(S[i:i+j]) % 2019 == 0:
            count += 1

print(count)

### FIXED CODE ###

S = input()

n = len(S)
m = 2019

S_ = S[::-1]

x = 1
total = 0
modlis = [0 for i in range(m)]

ans = 0
for i in range(n):
    modlis[total] += 1
    #print("S_[i]:", S_[i])
    #print("int(S_[i])*x:", int(S_[i])*x)
    #print("total:", total)
    total += int(S_[i])*x
    #print("total:", total)
    total %= m
    #print("total:", total)
    ans += modlis[total]
    #print("x:", x)
    x = x * 10 % m
    #print("x:", x)

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

import sys
input = sys.stdin.buffer.readline
R,C,K = map(int,input().split())
goods = [[-1]*(C+1) for _ in range(R+1)]
INF = 10**16
for i in range(K):
    ri,ci,vi = map(int,input().split())
    goods[ri][ci] = vi
DP = [[[-INF,-INF,-INF,-INF] for _ in range(C+1)] for _ in range(R+1)]
DP[1][1][0] = 0
if goods[1][1] != -1:
    DP[1][1][1] = goods[1][1]
for j in range(1,C):
    DP[1][j+1][0] = 0
    if goods[1][j+1] != -1:
        DP[1][j+1][1] = max(DP[1][j][1],DP[1][j][0]+goods[1][j+1])
        DP[1][j+1][2] = max(DP[1][j][2],DP[1][j][1]+goods[1][j+1])
        DP[1][j+1][3] = max(DP[1][j][3],DP[1][j][2]+goods[1][j+1])
    else:
        DP[1][j+1][1] = DP[1][j][1]
        DP[1][j+1][2] = DP[1][j][2]
        DP[1][j+1][3] = DP[1][j][3]
for i in range(1,R):
    DP[i+1][1][0] = max(DP[i][1])
    if goods[i+1][1] != -1:
        DP[i+1][1][1] = DP[i+1][1][0] + goods[i+1][1]
for i in range(2,R+1):
    for j in range(2,C+1):
        DP[i][j][0] = max(max(DP[i-1][j]),DP[i][j-1][0])
        if goods[i][j] != -1:
            DP[i][j][1] = max(DP[i][j][0]+goods[i][j],DP[i][j-1][1])
            DP[i][j][2] = max(DP[i][j-1][2],DP[i][j-1][1]+goods[i][j])
            DP[i][j][3] = max(DP[i][j-1][3],DP[i][j-1][2]+goods[i][j])
        else:
            DP[i][j][1] = DP[i][j-1][1]
            DP[i][j][2] = DP[i][j-1][2]
            DP[i][j][3] = DP[i][j-1][3]
print(max(DP[R][C]))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
R,C,K = map(int,input().split())
goods = [[0]*(C+1) for _ in range(R+1)]
INF = 10**18
for i in range(K):
    ri,ci,vi = map(int,input().split())
    goods[ri][ci] = vi
DP = [[[-INF]*(C+1) for _ in range(R+1)] for _ in range(4)]
DP[0][1][1] = 0
if goods[1][1]:
    DP[1][1][1] = goods[1][1]
for j in range(1,C):
    DP[0][1][j+1] = 0
    if goods[1][j+1]:
        DP[1][1][j+1] = max(DP[1][1][j],DP[0][1][j]+goods[1][j+1])
        DP[2][1][j+1] = max(DP[2][1][j],DP[1][1][j]+goods[1][j+1])
        DP[3][1][j+1] = max(DP[3][1][j],DP[2][1][j]+goods[1][j+1])
    else:
        DP[1][1][j+1] = DP[1][1][j]
        DP[2][1][j+1] = DP[2][1][j]
        DP[3][1][j+1] = DP[3][1][j]
for i in range(1,R):
    DP[0][i+1][1] = max(DP[0][i][1],DP[1][i][1],DP[2][i][1],DP[3][i][1])
    if goods[i+1][1]:
        DP[1][i+1][1] = DP[0][i+1][1] + goods[i+1][1]
for i in range(2,R+1):
    for j in range(2,C+1):
        DP[0][i][j] = max(DP[0][i-1][j],DP[1][i-1][j],DP[2][i-1][j],DP[3][i-1][j],DP[0][i][j-1])
        if goods[i][j]:
            DP[1][i][j] = max(DP[0][i][j]+goods[i][j],DP[1][i][j-1])
            DP[2][i][j] = max(DP[2][i][j-1],DP[1][i][j-1]+goods[i][j])
            DP[3][i][j] = max(DP[3][i][j-1],DP[2][i][j-1]+goods[i][j])
        else:
            DP[1][i][j] = DP[1][i][j-1]
            DP[2][i][j] = DP[2][i][j-1]
            DP[3][i][j] = DP[3][i][j-1]
print(max(DP[0][R][C],DP[1][R][C],DP[2][R][C],DP[3][R][C]))