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

from sys import stdin
from sys import setrecursionlimit
from collections import Counter
setrecursionlimit(10 ** 7)

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

q = int(input())
cc = Counter(a)

for _ in range(q):
    b,c = map(int,input().split())
    cc[c] += cc[b]
    cc[b] -= cc[b]
    su = 0
    for i,j in cc.items():
        su += i*j
    print(su)

### FIXED CODE ###

from sys import stdin
from sys import setrecursionlimit
from collections import Counter
setrecursionlimit(10 ** 7)

n = int(input())
a = list(map(int,stdin.readline().rstrip().split()))
su = sum(a)

q = int(input())
cc = Counter(a)

for _ in range(q):
    b,c = map(int,input().split())
    cc[c] += cc[b]
    su += c*cc[b]-b*cc[b]
    cc[b] -= cc[b]
    print(su)
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
kinds = len(set(A))
count = []

for i in set(A):
  count.append(A.count(i))

rest = kinds - K
if rest > 0: 
  print(sum(sorted(count)[:rest]))
else: 
  print(0)





### FIXED CODE ###

from collections import Counter
N,K = map(int,input().split())
A = Counter(list(map(int,input().split())))
V = []
for v in A.values():
    V.append(v)
V.sort(reverse = 1)
print(sum(V[K:]))
### BUGGY CODE ###

k = int(input())

a = 7
for i in range(k):
  if a % k == 0:
    print(i+1)
    exit()
  else:
    i += 1
    a += 7*(10**i)
print(-1)

### FIXED CODE ###

k = int(input())
 
a = 7
for i in range(k):
  if a % k == 0:
    print(i+1)
    break
  a = (10*a+7) % k
else:
  print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def sol():
    _, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    AF = [(a, f) for a, f in zip(sorted(A), sorted(F, reverse=True))]

    def isOk(T):
        ret = 0
        for a, f in AF:
            m = T // f
            if a > m:
                ret += a - T // f
        return ret <= K

    ok = max(a * f for a, f in AF)
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isOk(mid):
            ok = mid
        else:
            ng = mid

    print(ok)

sol()


### FIXED CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    _, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    A.sort()
    F.sort(reverse=True)

    def isOk(t):
        cnt = 0
        for a, f in zip(A, F):
            ness = t // f
            if a <= ness:
                continue
            cnt += a - ness

        if cnt > K:
            return False
        else:
            return True

    ng = -1
    ok = max(A) * max(F) + 10

    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isOk(mid):
            ok = mid
        else:
            ng = mid
    print(ok)


sol()
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

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

    sum=[0]*n
    sum[0]=a[0]
    for i in range(1,n):
        sum[i]=sum[i-1]*a[i]
        p=[0]*n
    for i in range(k-1,n):
        if i==k-1:
            p[i]=sum[i]
        else:
            p[i]=sum[i]/sum[i-k]


    for i in range(k,n):
        if p[i]>p[i-1]:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

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

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

sum=0
for i in range(K):
    if A>0:
        sum+=1
        A-=1
    elif B>0:
        B-=1
    elif C>0:
        sum-=1
        
print(sum)

### FIXED CODE ###

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

if K<=A:
    print(1*(K))
elif K<=A+B:
    print(1*(A))
elif K>A+B: 
    print(1*(A)+(-1)*(K-A-B))
### BUGGY CODE ###

numMultiples=0
S=input()
N=len(S)
seenRemainders=[set()]*(N+1)
for i in range(N):
    remainder = 0
    prefixesFound = 0
    for j in range(i,N):
        remainder = (10 * remainder + int (S[j]) ) % 2019
        # if remainder in seenRemainders[j]:
        #     break
        seenRemainders[j].add(remainder)
        if remainder == 0:
            prefixesFound+=1
    numMultiples += prefixesFound * (prefixesFound + 1) / 2
print(int(numMultiples))

### FIXED CODE ###

S=input()[::-1]
l=len(S)
t=0
p=0
 
ss=[0]*2019
ss[0]=1
d=1
for i in S:
    p=(p+int(i)*d)%2019
    d*=10
    d%=2019
    ss[p]+=1
 
for c in ss:
    t+=c*(c-1)//2
print(t)
### BUGGY CODE ###

import sys
import math
import numpy as np
import bisect
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, m = na()
a = na()
a.sort()
a = np.array(a, dtype="int64")
for _ in range(m):
    bi, ci = na()
    index = bisect.bisect_left(a,ci) - 1
    if index  < bi:
        a[:(index+1)] = ci
    else:
        b = a[bi:(index+1)]
        a[:(index-bi)+1] = b
        a[(index-bi)+1:(index+1)] = ci
print(sum(a))

### FIXED CODE ###

import sys
import math
import numpy as np
import bisect
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, m = na()
a = na()
bc = []

for _ in range(m):
    bci = na()
    bc.append(bci)

bc.sort(key=lambda x:x[1], reverse=True)
#print(bc)

bi, ci = bc[0][0], bc[0][1]
i = 0
for _ in range(n):
    if bi != 0:
        bi -= 1
        a.append(ci)
    else:
        i += 1
        if i > (m - 1):
            break
        else:
            bi, ci = bc[i][0], bc[i][1]
            bi -= 1
            a.append(ci)

a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    temp=[0 for i in range(N)]
    for j in many_int():
        temp[N-j-1]=1
    treasures.append("".join(list(map(str,temp))))

dp=[10**15 for i in range(2**N)]
dp[0]=0

for i in range(2**N):
    for j in range(M):
        new_i = int(bin(int(treasures[j],2) | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

goal_index=2**N-1
if dp[goal_index]!=10**15:
    print(dp[goal_index])
else:
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]
    check={}

    for i in range(M):
        mon,_ =two_int()
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        
        if sums in check:
            if check[sums] > mon:
                check[sums]=mon
        else:
            check[sums]=mon
            
    for k,v in check.items():
        key_list.append(v)
        treasures.append(k)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp[0]=0
    M=len(key_list)

    for i in range(max_index-1):
        for j in range(M):
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            dp[new_i] = min(dp[new_i], cost) 
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()
### BUGGY CODE ###

def rabin_karp(T, P, d, q):
    n = len(T)
    m = len(P)
    if n < m:
        return
    h = 1
    p = 0
    t0 = 0
    #for _ in range(m - 1):
    #    h = int((h * d) % q)
    h = int(pow(d, m - 1))
    for i in range(m):
        p = int((d * p + P[i]) % q)
        t0 = int((d * t0 + T[i]) % q)
    # print("h = ", h)
    # print("p = ", p)
    for s in range(n - m + 1):
        # print("t0 = ", t0)
        if p == t0:
            for i in range(m):
                if P[i] != T[s + i]:
                    # print(i, s+i)
                    break
                if i == m - 1:
                    print(s)
        if s < n - m:
            # print("     ", t0 - T[s] * h)
            # print("     ",  d)
            # print("     ", T[s + m])
            t0 = int((d * (t0 - T[s] * h) + T[s + m]) % q)


d = 999999937
q = 1000000007
t = list(map(ord, input()))
p = list(map(ord, input()))

rabin_karp(t, p, d, q)


### FIXED CODE ###

def compute_prefix_function(p):
    m = len(p)
    pi = [0 for _ in range(m + 1)]
    pi[1] = 0
    k = 0
    for q in range(2, m + 1):
        while k > 0 and p[k] != p[q - 1]:
            k = pi[k]
        if p[k] == p[q - 1]:
            k += 1
        pi[q] = k
    return pi


def kmp_matcher(t, p):
    n = len(t)
    m = len(p)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(1, n + 1):
        while q > 0 and p[q] != t[i - 1]:
            q = pi[q]
        if p[q] == t[i - 1]:
            q += 1
        if q == m:
            print(i - m)
            q = pi[q]


t = input()
p = input()
kmp_matcher(t, p)
### BUGGY CODE ###

s = input()
t = input()
LENs = len(s)
LENt = len(t)
dp = [[0 for i in range(LENt+1)] for j in range(LENs+1)]
for i in range(LENs+1):
    for j in range(LENt+1):
        if i+1 <= LENs:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if j+1 <= LENt:
            dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if i+1 <= LENs and j+1<=LENt:
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1

ans = ''
x = LENs
y = LENt
while True:
    if len(ans)==dp[-1][-1]:
        break
    if dp[x-1][y] < dp[x][y-1]:
        y = y-1
    elif dp[x-1][y] > dp[x][y-1]:
        x = x-1
    elif dp[x-1][y-1]+1== dp[x][y]:
        ans =s[x-1] + ans
        x = x-1
        y = y-1
        continue
        
print(ans)

### FIXED CODE ###

s = input()
t = input()
LENs = len(s)
LENt = len(t)
dp = [[0 for i in range(LENt+1)] for j in range(LENs+1)]
for i in range(LENs+1):
    for j in range(LENt+1):
        if i+1 <= LENs:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if j+1 <= LENt:
            dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if i+1 <= LENs and j+1<=LENt:
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1

ans = ''
x = LENs
y = LENt
while True:
    if len(ans)==dp[-1][-1]:
        break
    if dp[x-1][y] ==dp[x][y]:
        x = x-1
    elif dp[x][y] == dp[x][y-1]:
        y = y-1
    elif dp[x-1][y-1]+1== dp[x][y]:
        ans =s[x-1] + ans
        x = x-1
        y = y-1
        continue
#     elif dp[x-1][y] == dp[x][y-1]:
#         x = x-1

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

l, r = map(int,input().split())
ans = 2019
for i in range(l, r) :
    for j in range(i + 1, r + 1) :
        ans = min(ans, (i * j) % 2019)
print(ans)

### FIXED CODE ###

l, r = map(int,input().split())
ans = 2019
for i in range(l, r) :
    for j in range(i + 1, r + 1) :
        ans = min(ans, (i * j) % 2019)
        if ans == 0 : 
            break
    if ans == 0 :
        break
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = []
for i in a:
    b.append(i)
    b = list(reversed(b))
b = [str(b_) for b_ in b]
ans = " ".join(b)
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
e = [a[i] for i in range(n) if i % 2 == 1]
o = [a[i] for i in range(n) if i % 2 == 0]
if (n % 2 == 1):
    ans = o[::-1] + e
else:
    ans = e[::-1] + o
ans = [str(i) for i in ans]
ans = " ".join(ans)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)
from collections import Counter

N = int(input())
a = list(map(int, input().split()))
c = Counter(a)
one, two, three = c[1], c[2], c[3]
dp = [[[-1 for i in range(three + 1)] for j in range(N+1)] for k in range(N+1)]

def rec(i, j, k):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0
    if i > 0:
        res += rec(i-1, j, k) * i
    if j > 0:
        res += rec(i+1, j-1, k) * j
    if k > 0:
        res += rec(i, j+1, k-1) * k
    res += N
    res /= i+j+k
    dp[i][j][k] = res
    return res

rec(one, two, three)
print(dp[one][two][three])


### FIXED CODE ###

import sys
from collections import Counter
sys.setrecursionlimit(10000)

N = int(input())
a = list(map(int, input().split()))
dp = [[[-1 for i in range(N+1)] for j in range(N+1)] for k in range(N+1)]

def rec(i, j, k):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0
    if i > 0:
        res += rec(i-1, j, k) * i
    if j > 0:
        res += rec(i+1, j-1, k) * j
    if k > 0:
        res += rec(i, j+1, k-1) * k
    res += N
    res *= 1.0/(i+j+k)

    dp[i][j][k] = res
    return res

c = Counter(a)
one, two, three = c[1], c[2], c[3]
print(rec(one, two, three))
### BUGGY CODE ###

L, R = [int(i) for i in(input().split(' '))]
minn=2019
for i in range(L,R):
    for j in range(i+1,R+1):
        mo = i*j
        amari = mo%2019
        minn = min(amari,minn)
print(minn)

### FIXED CODE ###

L, R = [int(i) for i in(input().split(' '))]
minn=2019
if R-L+1>2019:
  print(0)
  exit()
for i in range(L,R):
    for j in range(i+1,R+1):
        mo = i*j
        amari = mo%2019
        minn = min(amari,minn)
        if minn==0:
          break
print(minn)
### BUGGY CODE ###

n = int(input())
x = [int(input()) for i in range(n)]
y = [j for j in set(x) if x.count(j) > 1]
z = [k for k in set(x) if x.count(k) == 1]
cnt = len(z)
for i in range(len(y)):
    if x.count(y[i]) % 2 == 1:
        cnt += 1
print(cnt)

### FIXED CODE ###

import collections
n = int(input())
x = [int(input()) for i in range(n)]
c = collections.Counter(x)
cc = list(c.values())
cnt = 0
for i in range(len(cc)):
    if cc[i] % 2 == 1:
        cnt += 1
print(cnt)
### BUGGY CODE ###

from collections import defaultdict
n, q = map(int, input().split())
child_dict = defaultdict(set)
value_dict = defaultdict(lambda: 0)
for _ in range(n - 1):
    a, b = map(int, input().split())
    child_dict[a].add(b)
import copy
for _ in range(q):
    c, d = map(int, input().split())
    value_dict[c] += d
    child = child_dict[c]
    while len(child) > 0:
        k = []
        for i in child:
            value_dict[i] += d
            k.extend(child_dict[i])
        child = copy.deepcopy(k)
ans = [value_dict[i] for i in range(1 ,n+1)]
print(*ans)



### FIXED CODE ###

n, q = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
point_list = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    p -= 1
    point_list[p] += x

from collections import deque
d = deque()
d.append(0)
visited = set([])

while d:
    x = d.popleft()
    for child in graph[x]:
        if child not in visited:
            point_list[child] += point_list[x]
            d.append(child)
        visited.add(x)
print(*point_list)
### BUGGY CODE ###

n,m,q=map(int,input().split())
counts=[[0 for _ in range(n)]for _ in range(n)]

for _ in range(m):
    l,r=map(int,input().split())
    for i in range(l):
        for j in range(r-1,n):
            counts[i][j]+=1
for _ in range(q):
    l,r=map(int,input().split())
    print(counts[l-1][r-1])

### FIXED CODE ###

n,m,q=map(int,input().split())
counts=[[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    l,r=map(int,input().split())
    counts[l-1][r-1]+=1
cumsum=[[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        cumsum[i+1][j+1]=cumsum[i+1][j]+counts[i][j]
for j in range(n+1):
    for i in range(n):
        cumsum[i+1][j]+=cumsum[i][j]
        
for _ in range(q):
    l,r=map(int,input().split())
    print(cumsum[r][r]-cumsum[r][l-1]-cumsum[l-1][r]+cumsum[l-1][l-1])
### BUGGY CODE ###

n, k = [int(w) for w in input().split()]
la = [int(w) for w in input().split()]

mul = 1
for i in range(k-1):
    mul *= la[i]


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

for i in range(n-k+1):
    score[i] = mul*la[i+k-1]


for i in range(k-1, n):
    mul *= la[i]
    score[i-k+1] = mul
    mul /= la[i-k+1]

for i in range(1, len(score)):
    cond = score[i] > score[i-1]
    print("Yes" if cond else "No")


### FIXED CODE ###

n, k = [int(w) for w in input().split()]
la = [int(w) for w in input().split()]


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

N = int(input())
s = input()
ans = 0
for a2 in range(10):
    for b2 in range(10):
        for c2 in range(10):
            a = str(a2)
            count = 0
            for i in s:
                if a == i:
                    count += 1
                    if count == 1:
                        a = str(b2)
                    if count == 2:
                        a = str(c2)
                    if count == 3:
                        break
            if count == 3:
                ans += 1
print(ans)

### FIXED CODE ###

from itertools import combinations
N = int(input())
s = input()
ans = 0
for a2 in range(10):
    for b2 in range(10):
        for c2 in range(10):
            a = str(a2)
            b = str(b2)
            c = str(c2)
            count = 0
            for i in s:
                if a == i:
                    count += 1
                    if count == 1:
                        a = b
                    if count == 2:
                        a = c
            if count >= 3:
                ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))

for i in range(N):
    tmp,a[i] = a[i],0
    print(max(a))
    a[i] = tmp

### FIXED CODE ###

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))

sorted_list = sorted(a,reverse=True)
first = sorted_list[0]
secend = sorted_list[1]

for num in a:
    if num != first:
        print(first)
    else:
        print(secend)
### BUGGY CODE ###

s = list(input())
q = int(input())

reverse_flag = False

top = []
last = []
for i in range(q):
  q_list = list(input().split())
  
  if len(q_list) == 1:
    reverse_flag = not reverse_flag
    
  elif q_list[1] == '1' and (not reverse_flag):
    top.insert(0, q_list[2])
    
  elif q_list[1] == '2' and (not reverse_flag):
    last.append(q_list[2])
    
  elif q_list[1] == '1' and reverse_flag:
    last.append(q_list[2])
    
  elif q_list[1] == '2' and reverse_flag:
    top.insert(0, q_list[2])
    
if reverse_flag:
  print(''.join(reversed(last)) + ''.join(reversed(s)) + ''.join(reversed(top)))
else:
  print(''.join(top) + ''.join(s) + ''.join(last))

### FIXED CODE ###

s = list(input())
q = int(input())

reverse_flag = False

top = []
last = []
for i in range(q):
  q_list = list(input().split())
  
  if len(q_list) == 1:
    reverse_flag = not reverse_flag
    
  elif q_list[1] == '1' and (not reverse_flag):
    top.append(q_list[2])
    
  elif q_list[1] == '2' and (not reverse_flag):
    last.append(q_list[2])
    
  elif q_list[1] == '1' and reverse_flag:
    last.append(q_list[2])
    
  elif q_list[1] == '2' and reverse_flag:
    top.append(q_list[2])
    
if reverse_flag:
  print(''.join(reversed(last)) + ''.join(reversed(s)) + ''.join(top))
else:
  print(''.join(reversed(top)) + ''.join(s) + ''.join(last))
### BUGGY CODE ###

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

mev = 0

for i in range(N-K+1):

    ev = sum(map(lambda x: (x+1.0)/2.0, p[i:i+K]))

    if ev > mev:
        mev = ev

print(mev)


### FIXED CODE ###

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

#累積和を前計算
sum_list = [0 for _ in range(300000)]
sum = 0

for i in range(len(p)):
    sum += p[i]
    sum_list[i] = sum

#答えを計算
mev = 0
idx = 0
for i in range(N-K+1):
    ev = sum_list[i+K]-sum_list[i]
    if ev > mev:
        idx = i
        mev = ev

mev = 0.0
if N != K:
    for i in range(idx+1,idx+1+K):
        mev += (p[i] + 1.0) / 2.0

else:
    for i in range(len(p)):
        mev += (p[i] + 1.0) / 2.0

print(mev)
### BUGGY CODE ###

import sys

def calc(a, H, W):
    # 横方向
    for j in range(H):
        prev = 0
        start = 0
        for i in range(W + 1):
            if a[j][i] > 0:
                if prev == 0:
                    start = i
                    prev = 1
            else:
                if prev == 1:
                    num = i - start
                    for k in range(start, i):
                        a[j][k] = num
                    prev = 0
    # 縦方向
    for i in range(W):
        prev = 0
        start = 0
        for j in range(H + 1):
            if a[j][i] > 0:
                if prev == 0:
                    start = j
                    prev = 1
            else:
                if prev == 1:
                    num = j - start
                    for k in range(start, j):
                        a[k][i] += num - 1
                    prev = 0


sin = sys.stdin
H, W = map(int, sin.readline().split())
a = [[0] * (W + 1) for _ in range(H + 1)]

for j in range(H):
    for i, c in enumerate(sin.readline()):
        if c == '.':
            a[j][i] = 1

calc(a, H, W)

ans = 0
for row in a:
    ans = max(ans, max(row))
print(ans)


### FIXED CODE ###

import numpy as np
import sys


def get_data(stream):
    buf = b''
    b = stream.buffer.read(1)
    while b != b'\n':
        buf += b
        b = stream.buffer.read(1)
    H, W = map(int, buf.split())
    c = stream.buffer.read(H * (W + 1))
    arr = np.array(c.split())
    arr = np.frombuffer(arr, dtype='S1').reshape((H, W))
    return H, W, arr


def main():
    H, W, arr = get_data(sys.stdin)
    a = arr == b'.'
    L = np.empty((H, W), dtype='i8')
    R = np.empty((H, W), dtype='i8')
    T = np.empty((H, W), dtype='i8')
    B = np.empty((H, W), dtype='i8')
    T[0] = a[0]
    for i in range(1, H):
        T[i] = (T[i - 1] + 1) * a[i]
    B[-1] = a[-1]
    for i in range(H - 2, -1, -1):
        B[i] = (B[i + 1] + 1) * a[i]
    L[:, 0] = a[:, 0]
    for i in range(1, W):
        L[:, i] = (L[:, i - 1] + 1) * a[:, i]
    R[:, -1] = a[:, -1]
    for i in range(W - 2, -1, -1):
        R[:, i] = (R[:, i + 1] + 1) * a[:, i]

    print((T + B + L + R - 3).max())


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

R,C,K=map(int,input().split())
value=[[0]*(C+1) for i in range(R+1)]
for i in range(K):
  r,c,v=map(int,input().split())
  value[r][c]=v
DP0=[[0]*(C+1) for i in range(R+1)]
DP1=[[0]*(C+1) for i in range(R+1)]
DP2=[[0]*(C+1) for i in range(R+1)]
DP3=[[0]*(C+1) for i in range(R+1)]
for i in range(1,R+1):
  for j in range(1,C+1):
    DP0[i][j]=max(DP0[i][j-1],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])
    DP1[i][j]=max(DP0[i-1][j]+value[i][j],DP1[i-1][j]+value[i][j],DP2[i-1][j]+value[i][j],
                  DP3[i-1][j]+value[i][j],DP1[i][j-1],DP0[i][j-1]+value[i][j])
    DP2[i][j]=max(DP1[i][j-1]+value[i][j],DP2[i][j-1])
    DP3[i][j]=max(DP2[i][j-1]+value[i][j],DP3[i][j-1])

    
print(max(DP0[R][C],DP1[R][C],DP2[R][C],DP3[R][C]))

### FIXED CODE ###

R,C,K=map(int,input().split())
value=[[0]*(C+1) for i in range(R+1)]
for i in range(K):
  r,c,v=map(int,input().split())
  value[r][c]=v
DP0=[[0]*(C+1) for i in range(R+1)]
DP1=[[0]*(C+1) for i in range(R+1)]
DP2=[[0]*(C+1) for i in range(R+1)]
DP3=[[0]*(C+1) for i in range(R+1)]
for i in range(1,R+1):
  for j in range(1,C+1):
    v=value[i][j]
    a=DP0[i][j-1]
    b=DP1[i][j-1]
    c=DP1[i-1][j]
    d=DP2[i-1][j]
    e=DP3[i-1][j]
    f=DP2[i][j-1]
    DP0[i][j]=max(a,c,d,e)
    DP1[i][j]=max(DP0[i-1][j]+v,c+v,d+v,e+v,b,a+v)
    DP2[i][j]=max(b+v,f)
    DP3[i][j]=max(f+v,DP3[i][j-1])

print(max(DP0[R][C],DP1[R][C],DP2[R][C],DP3[R][C]))