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

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


dp=[0]+[float("inf")]*(N-1)


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

print(dp[-1])

### FIXED CODE ###

N,K=list(map(int, input().split()))
h=list(map(int, input().split()))
 
 
dp=[0]+[float("inf")]*(N-1)
 
 
for i in range(N-1):
    for j in range(i,i+K):
        if j+1>N-1:
            break
        dp[j+1]=min(abs(h[j+1]-h[i])+dp[i],dp[j+1])
    
 
print(dp[-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

blocks_table = [[] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    blocks_table[a-1] += [b-1]
    blocks_table[b-1] += [a-1]

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    friend = [i]
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = friends_table[i][:]
    while next_stack:
        next = next_stack.pop()
        # 訪問済み
        if i == group_list[next]:
            continue
        friend += [next]
        group_list[next] = i
        next_stack += friends_table[next]
    for f in friend:
        friends_candidate[f] = friend

for i in range(N):
    print(len(set(friends_candidate[i]).difference(set(friends_table[i] + blocks_table[i])))-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = [i]
    friend = [i]
    while next_stack:
        u = next_stack.pop(-1)
        for v in friends_table[u]:
            # 訪問済み
            if i == group_list[v]:
                continue
            friend += [v]
            group_list[v] = i
            next_stack += [v]
    for f in friend:
        friends_candidate[f] = friend

blocks_table = [[] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    if group_list[a-1] == group_list[b-1]:
        blocks_table[a-1] += [b-1]
        blocks_table[b-1] += [a-1]

for i in range(N):
    print(len(friends_candidate[i]) - len(friends_table[i]) - len(blocks_table[i])-1)
### BUGGY CODE ###


def pr(a):
    for i in range(len(a)):
        print(a[i],end="")
        if i == len(a)-1:
            print("")
        else :
            print(" ",end="")

n = int(input())
a = []
for i in range(n):
    x = input().split()
    if x[0] == "insert":
        a.insert(0,int(x[1]))
    elif x[0] == "delete":
        if int(x[1]) in a:
            a.remove(int(x[1]))
    elif x[0] == "deleteFirst":
        a.pop(0)
    elif x[0] == "deleteLast":
        a.pop()

pr(a)



### FIXED CODE ###

from collections import deque

def pr(a):
    for i in range(len(a)):
        if i == len(a)-1:
            print(a[i])
        else:
            print(a[i],end = " ")

n = int(input())
q = deque()
for i in range(n):
    x = input()
    l = len(x)
    if x[0] == "i":
        q.insert(0,x[7:])
    elif x[6] == " ":
        try:
            q.remove(x[7:])
        except:
            pass
    elif l > 10:
        q.popleft()
    elif l > 6:
        q.pop()

print(*q)
### BUGGY CODE ###

import bisect

N, M = [int(i) for i in input().split()]
alist = [int(i) for i in input().split()]
inputs = [[int(i) for i in input().split()] for _ in range(M)]

alist.sort()

for i in inputs:
    index=bisect.bisect_left(alist, i[1])
    limit = index if index < i[0] else i[0]
    for r in range(limit):
        alist[r]=i[1]
    alist.sort()

print(sum(alist))




### FIXED CODE ###

import bisect

N, M = [int(i) for i in input().split()]
alist = [int(i) for i in input().split()]
alist.sort()
inputs = [[int(i) for i in input().split()] for j in range(M)]
inputs.sort(key=lambda x:x[1], reverse=True)

for i in range(N):
    if len(inputs) == 0:
        break
    if inputs[0][1] > alist[i]:
        alist[i] = inputs[0][1]
        inputs[0][0] -= 1
        if inputs[0][0] == 0:
            inputs.pop(0)
    else:
        break
print(sum(alist))
### BUGGY CODE ###

n = int(input())
s = list(map(int,input().split()))
t = {}
o = 0
for i in range(n):
    if s[i] not in t.keys():
        t[s[i]] = 1
    else:
        t[s[i]] += 1

for i,j in t.items():
    if i > j:
        o += j
    else:
        o += j - i

print(o)

### FIXED CODE ###

n = int(input())
s = list(map(int,input().split()))
t = {}
o = 0
for i in range(n):
    if s[i] not in t.keys():
        t[s[i]] = 1
    else:
        t[s[i]] += 1

for i,j in t.items():
    if i > j:
        o += j
    else:
        o += j - i

print(o)
### BUGGY CODE ###

N = int(input())
list_A = [int(input()) for i in range(N)]

list_X = []

for A in list_A :
    if A in list_X :
        list_X.remove(A)
    else :
        list_X.append(A)

print(len(list_X))


### FIXED CODE ###

N = int(input())
list_A = [int(input()) for i in range(N)]

from collections import Counter
list_X = Counter(list_A).values()

ans = 0
for X in list_X :
    if X%2 == 1 :
        ans += 1

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

import numpy as np
from collections import Counter as C

n=int(input())
a = list(input().split())
a = [int(i) for i in a]
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
bc=np.array(bc).T
b=bc[0]
c=bc[1]

d=C(a)
d2={}
for k,v in d.items():
  d2[k]=k*v

#print(d)
for i in range(q):
  ans=0
  #print(d2)
  for k,v in d.items():
    if k==b[i]:
      #print("b[i]",b[i])
      removed=d.pop(b[i])
      no=d2.pop(b[i])
      d[c[i]]+=removed
      d2[c[i]]=c[i]*d[c[i]]
      break
  print(sum(d2.values()))
  


### FIXED CODE ###

import numpy as np
from collections import Counter as C

n=int(input())
a = list(input().split())
a = [int(i) for i in a]
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
bc=np.array(bc).T
b=bc[0]
c=bc[1]

d=C(a)
d2={}
for k,v in d.items():
  d2[k]=k*v

#print(d)
ans=sum(a)
for i in range(q):
  d[c[i]]+=d[b[i]]
  ans+=(c[i]-b[i])*d[b[i]]
  d[b[i]]=0
  print(ans)
### BUGGY CODE ###

n = int(input())
a_list = list(map(int,input().split()))
result = 1
for a in a_list:
  result = result * a
  
if result > 10**18:
  print(-1)
else:
  print(result)

### FIXED CODE ###

n = int(input())
a_list = list(map(int,input().split()))
result = 1
if 0 in a_list:
  print(0)
else:
  for a in a_list:
    result = result *a
    if len(str(result)) >= 19:
      if result == 10**18:
        continue
      else:
        result = -1
        break
        
  print(result)
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())

adj = [[float("inf") for i in range(N)] for j in range(N)]
signs = [-1 for i in range(N)]
not_patrolled = set(range(1, N))

for _ in range(M):
  x,y = map(int,input().split())
  adj[x - 1][y - 1] = 1
  adj[y - 1][x - 1] = 1

queue = deque([0])

while len(queue) > 0:
  cur = queue.popleft()
  for i in not_patrolled.copy():
    c = adj[cur][i]
    if c == 1:
      queue.append(i)
      signs[i] = cur
      not_patrolled.remove(i)

if len(not_patrolled) == 0:
  print("Yes")
  for sign in signs[1:]:
    print(sign + 1)
else:
  print("No")

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())

adj = [[] for i in range(N)]
signs = [-1 for i in range(N)]
# not_patrolled = set(range(1, N))

for _ in range(M):
  x,y = map(int,input().split())
  adj[x - 1].append(y - 1)
  adj[y - 1].append(x - 1)

queue = deque([0])

while len(queue) > 0:
  cur = queue.popleft()
  for i in adj[cur]:
    if signs[i] == -1:
      queue.append(i)
      signs[i] = cur
      # not_patrolled.remove(i)

if all([sign != -1 for sign in signs[1:]]):
  print("Yes")
  for sign in signs[1:]:
    print(sign + 1)
else:
  print("No")
### BUGGY CODE ###

h, w, m = map(int, input().split())
s = [[False] * w for _ in range(h)]
num_h = [0] * h
num_w = [0] * w
for _ in range(m):
    hi, wi = map(int, input().split())
    hi -= 1
    wi -= 1
    s[hi][wi] = True
    num_h[hi] += 1
    num_w[wi] += 1
max_h_list = []
max_h_val = 0
max_w_list = []
max_w_val = 0
for hi in range(h):
    if num_h[hi] > max_h_val:
        max_h_list = [hi]
        max_h_val = num_h[hi]
    elif num_h[hi] == max_h_val:
        max_h_list.append(hi)
for wi in range(w):
    if num_w[wi] > max_w_val:
        max_w_list = [wi]
        max_w_val = num_w[wi]
    elif num_w[wi] == max_w_val:
        max_w_list.append(wi)

for max_hi in max_h_list:
    for max_wi in max_w_list:
        if s[max_hi][max_wi] == False:
            print(max_h_val + max_w_val)
            exit()
print(max_h_val + max_w_val - 1)


### FIXED CODE ###

h, w, m = map(int, input().split())
s = dict()
num_h = [0] * h
num_w = [0] * w
for _ in range(m):
    hi, wi = map(int, input().split())
    hi -= 1
    wi -= 1
    s[(hi, wi)] = True
    num_h[hi] += 1
    num_w[wi] += 1
max_h_list = []
max_h_val = 0
max_w_list = []
max_w_val = 0
for hi in range(h):
    if num_h[hi] > max_h_val:
        max_h_list = [hi]
        max_h_val = num_h[hi]
    elif num_h[hi] == max_h_val:
        max_h_list.append(hi)
for wi in range(w):
    if num_w[wi] > max_w_val:
        max_w_list = [wi]
        max_w_val = num_w[wi]
    elif num_w[wi] == max_w_val:
        max_w_list.append(wi)

if len(max_h_list) * len(max_w_list) > m:
    print(max_h_val + max_w_val)
    exit()
for max_hi in max_h_list:
    for max_wi in max_w_list:
        if s.get((max_hi, max_wi), False) == False:
            print(max_h_val + max_w_val)
            exit()
print(max_h_val + max_w_val - 1)
### BUGGY CODE ###

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

a_sorted = sorted(a)
divisible_list = [True] * n

for i in range(n-1):
    if not divisible_list[i]:
        continue
    for j in range(i+1, n):
        if a_sorted[j] == a_sorted[i]:
            divisible_list[i] = False
            tmp = j
            while True:
                if tmp < n and a_sorted[tmp] == a_sorted[i]:
                    divisible_list[j] = False
                    tmp += 1
                else:
                    break

        elif a_sorted[j] % a_sorted[i] == 0:
            divisible_list[j] = False
print(sum(divisible_list))

### FIXED CODE ###

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

a_sorted = sorted(a)
divisible_list = [0] * (max(a)+1)

for i in range(len(a)):
    for j in range(0, len(divisible_list), a[i]):
        divisible_list[j] += 1

ans = 0
for i in range(len(a)):
    if divisible_list[a[i]] == 1:
        ans+=1
print(ans)
### BUGGY CODE ###

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

if N==1:
  if K%2:
    print(A[0])
  else:
    print('')
  exit()
  

#print(*range(10000))

def func(L):
  s = []
  for l in L:
    if l in s:
      del s[s.index(l):]
      #s_set.remove(l)
    else:
      s.append(l)
      #s_set.add(l)
  return s

index_dict={}

for i,a in enumerate(A):
  index_dict.setdefault(a,[]).append(i)

#print(index_dict)

from_in_cycle=[]

i = 0
while True:
  a = A[i]
  l = len(index_dict[a])
  j = index_dict[a].index(i)
  if j==l-1:
    from_in_cycle.append(i)
    i = (index_dict[a][0]+1)%N
  else:
    i = (index_dict[a][j+1]+1)%N
  # 循環の評価
  if i==0:
    break
    
#print(from_in_cycle)

if from_in_cycle:
  k = K%(len(from_in_cycle)+1)
  print(*func(A[from_in_cycle[k-1]:]))
else:
  print('')

### FIXED CODE ###

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

if N==1:
  if K%2:
    print(A[0])
  else:
    print('')
  exit()
  

#print(*range(10000))

def func(L):
  s = []
  for l in L:
    if l in s:
      del s[s.index(l):]
      #s_set.remove(l)
    else:
      s.append(l)
      #s_set.add(l)
  return s




index_dict={}
for i,a in enumerate(A):
  index_dict.setdefault(a,[]).append(i)

next_i = [0]*N
cycle_i = [0]*N
for k,v in index_dict.items():
  for i in range(len(v)):
    next_i[v[i]] = (v[(i+1)%len(v)]+1)%N
    cycle_i[v[i]] = (i+1)//len(v)
#print(next_i)
#print(cycle_i)

from_in_cycle=[]

i = 0
while True:
  j = next_i[i]
  if cycle_i[i]:
    from_in_cycle.append(i)
  i = j
  # 循環の評価
  if i==0:
    break
    
#print(from_in_cycle)

if from_in_cycle:
  k = K%(len(from_in_cycle)+1)
  #print(*func(A[from_in_cycle[k-1]:]))

  ans = []
  i = from_in_cycle[k-1]
  while i < N:
    if cycle_i[i]:
      ans.append(A[i])
      i += 1
    else:
      if next_i[i]==0:
        break
      i = next_i[i]
  print(*ans)


else:
  print('')
### BUGGY CODE ###

def digit_dp(n, m):
    # dp[i][j][k] -> i: 現在見ている桁数
    #                j: n以下が保証されているかどうか
    #                k: m で割った余りの総和
    n = list(map(int, list(str(n))))
    n_len = len(n)
    dp_table = [[[0 for k in range(m)] for j in range(2)] for i in range(n_len + 1)]
    dp_table[0][0][0] = 1

    for i in range(n_len):
        for j in range(2):
            for k in range(m):
                for d in range(0, 10 if j else n[i] + 1):
                    dp_table[i + 1][j or (d < n[i])][(k + d % m) % m] += dp_table[i][j][k]

    return dp_table[-1][0][0] + dp_table[-1][1][0] - 1
    #0 の分、1を減算


a = int(input())
b = int(input())
mod = 10**9 + 7
print(digit_dp(a, b) % mod)


### FIXED CODE ###

k = str(input())
d = int(input())

DP = [[[0 for _ in range(d)] for _ in range(2)] for _ in range(len(k)+1)]
DP[0][0][0] = 1

for i in range(len(k)):
    now = int(k[i])
    for j in range(2):
        for mod in range(d):
            for n in range(10):
                # 対象の数字未満が確定する場合
                if j==1 or (j==0 and n < now):
                    next_j = 1
                # 対象の数字とこの桁まで同じ場合
                elif n == now:
                    next_j = 0
                # 対象の数字よりも大きな値の場合
                else: 
                    continue

                n_mod = n % d
                next_mod = (mod + n_mod) % d
                DP[i+1][next_j][next_mod] = (DP[i+1][next_j][next_mod] + DP[i][j][mod]) % (10**9+7)

ans = (DP[len(k)][0][0] + DP[len(k)][1][0] -1) % (10**9+7)
print(ans)
# print(DP)
### BUGGY CODE ###

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

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
  p, q, c = map(int, input().split())
  p -= 1
  q -= 1
  G[p].append((q, c))
  G[q].append((p, c))
que = deque()
que.append((0, -1, 0))
dist = [float("inf")]*n
while que:
  v, com, cnt = que.popleft()
  if cnt > dist[v]:
    continue
  dist[v] = cnt
  for nv, ncom in G[v]:
    if ncom == com:
      que.appendleft((nv, ncom, cnt))
    else:
      que.append((nv, ncom, cnt+1))
if dist[-1] == float("inf"):
  print(-1)
else:
  print(dist[-1])

### FIXED CODE ###

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

n, m = map(int, input().split())
G = defaultdict(set)
U = 10**6
seen = set()
for _ in range(m):
  p, q, c = map(int, input().split())
  G[p+U*c].add((q+U*c, 0))
  G[q+U*c].add((p+U*c, 0))
  G[p+U*c].add((p-U, 0))
  G[q+U*c].add((q-U, 0))
  G[p-U].add((p+U*c, 1))
  G[q-U].add((q+U*c, 1))
que = deque()
que.append((1-U, 0))
while que:
  v, cnt = que.popleft()
  if v in seen:
    continue
  if v == n-U:
    print(cnt)
    exit()
  seen.add(v)
  for nv, cost in G[v]:
    if cost == 0:
      que.appendleft((nv, cnt+cost))
    else:
      que.append((nv, cnt+cost))
print(-1)
### BUGGY CODE ###

N, M = map(int, input().split())
l_1 = [[] for i in range(N+1)]
l_2 = []
P = []
for i in range(M):
  p, y = map(int, input().split())
  l_1[p].append(y)
  l_2.append([p, y])
  P.append(p)
  
P = set(P)
for i in P:
  l_1[i].sort()
    
for i in range(M):
  c = l_2[i]
  n = l_1[c[0]].index(c[1]) + 1
  ans = str(c[0]).zfill(6) + str(n).zfill(6)
  print(ans)


### FIXED CODE ###

import bisect
N, M = map(int, input().split())
l_1 = [[] for i in range(N+1)]
l_2 = []
for i in range(M):
  p, y = map(int, input().split())
  l_1[p].append(y)
  l_2.append([p, y])
  
for i in range(N+1):
  l_1[i].sort()
    
for i in range(M):
  c = l_2[i]
  n = bisect.bisect_left(l_1[c[0]], c[1]) + 1
  ans = str(c[0]).zfill(6) + str(n).zfill(6)
  print(ans)
### BUGGY CODE ###

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

result=abs(n-k)

while result > abs(result-k):
    result=abs(result-k)

print(result)

### FIXED CODE ###

n,k=map(int,input().split())
n=int(n%k)
result=abs(k-n)

if n==0:
    print(0)
else:
    while result > abs(result-k):
        result=abs(result-k)
    print(result)
### BUGGY CODE ###

def main(): #なんか早くなるおまじない
    import sys
    from collections import defaultdict
    dic = defaultdict(int)

    input = sys.stdin.readline #早くなるおまじない

    s = str(input().rstrip())
    m = 0

    for i in range(1, len(s) + 1):
        m_1 = pow(10, i-1) % 2019
        m_add = (int(s[-i]) * m_1) % 2019
        m = (m_add + m) % 2019
        dic[m] += 1

    ans1 = 0

    for x in dic.values():
        if x > 1:
            ans1 += x * (x - 1) // 2
    ans2 = dic[0]

    print(ans1 + ans2)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import sys
    from collections import defaultdict
    dic = defaultdict(int)

    input = sys.stdin.readline

    s = str(input().rstrip())
    m = 0
    before_m = 0.1

    for i in range(1, len(s) + 1):
        before_m = int(before_m*10)%2019
        m_ad = (int(s[-i]) * before_m) % 2019
        m = (m_ad + m) % 2019
        dic[m] += 1

    ans1 = 0

    for x in dic.values():
        if x > 1:
            ans1 += x * (x - 1) // 2
    ans2 = dic[0]

    print(ans1 + ans2)

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

import numpy as np
N,W = map(int,input().split())
l = [list(map(int,input().split()))for i in range(N)]
dp = np.zeros(shape=(N,W + 1),dtype = int)
for i in range(l[0][0],W + 1):
    dp[0][i] = l[0][1]
for i in range(1,N):
    for j in range(W + 1):
        if l[i][0] > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - l[i][0]] + l[i][1])
print(dp[N - 1][W])

### FIXED CODE ###

import numpy as np
N,W = map(int,input().split())
l = [list(map(int,input().split()))for i in range(N)]
dp = np.zeros(shape=(N,W + 1),dtype = int)
for i in range(l[0][0],W + 1):
    dp[0][i] = l[0][1]
for i in range(1,N):
    weight = l[i][0]
    value = l[i][1]
    dp[i][:weight] = dp[i - 1][:weight]
    dp[i][weight:] = np.maximum(dp[i - 1][weight:], value + dp[i - 1][:-weight])
print(dp[N - 1][W])
### BUGGY CODE ###

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

ans = 1

for i in range(1, N):
    if min(P[0:i]) >= P[i]:
        ans += 1

print(ans)

### FIXED CODE ###

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

ans = 1
mini = P[0]

for i in range(1, N):
    if P[i] < mini:
        mini = P[i]
        ans += 1

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

n,m=map(int,input().split())
lst=[int(input()) for i in range(m)]
DP=[0]*(n+1)
temp=0
DP[0]=1
for i in range(1, n+1):
  if i==1 and i not in lst:
    DP[i]=1
  elif i==1 and i in lst:
    DP[i]=0
  elif i in lst:
    DP[i]=0
  else:
    DP[i]=DP[i-1]+DP[i-2]
print(DP[n]%1000000007)

### FIXED CODE ###

N,M=map(int,input().split())
br=set([int(input()) for _ in range(M)])
dp=[0]*(N+1)
dp[0]=1
if not 1 in br:
    dp[1]=1
for i in range(2,N+1):
    if not i in br:
        dp[i]+=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1])
### BUGGY CODE ###

import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
# input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

h,w,k=map(int,input().split())
# R=[]
A=[[0]*w for i in range(h)]
dp=[[[0]*4 for j in range(w)] for i in range(h)]

for s in sys.stdin.readlines():
    x,y,v=map(int,s.split())
    x-=1;y-=1
    A[x][y]=v
    # dp[x][y][1]=v
    # dp[x][y][2]=v
    # dp[x][y][3]=v;
dp[0][0][1]=A[0][0]
for i in range(h):
    for j in range(w):
        for k in range(4):
            here=dp[i][j][k]
            if i<h-1:
                dp[i+1][j][0] = max(here,dp[i+1][j][0])
                dp[i+1][j][1] = max(here+A[i+1][j], dp[i+1][j][1])
            if j<w-1:
                dp[i][j+1][k] = max(dp[i][j+1][k], here)
                if k<=2:
                    dp[i][j+1][k+1]= max(dp[i][j+1][k+1],here+ A[i][j+1])
           

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


### FIXED CODE ###

import sys

R, C, K = map(int, input().split())
item = [[0] * (C + 1) for _ in range(R + 1)]  # dp配列と合わせるために, 0行目, 0列目を追加している.
for s in sys.stdin.readlines():
    r, c, v = map(int, s.split())
    item[r][c] = v

dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
for i in range(R + 1):
    for j in range(C + 1):
        for k in range(4):
            here = dp[k][i][j]
            # 次の行に移動する場合
            if i + 1 <= R:
                # 移動先のアイテムを取らない場合
                dp[0][i + 1][j] = max(dp[0][i + 1][j], here)
                # 移動先のアイテムを取る場合
                dp[1][i + 1][j] = max(dp[1][i + 1][j], here + item[i + 1][j])
            # 次の列に移動する場合
            if j + 1 <= C:
                # 移動先のアイテムを取らない場合
                dp[k][i][j + 1] = max(dp[k][i][j + 1], here)
                # 現在のkが3未満のときのみ, 移動先のアイテムを取ることが可能
                if k < 3:
                    dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], here + item[i][j + 1])
ans = 0
for k in range(4):
    ans = max(ans, dp[k][-1][-1])
print(ans)