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

import sys

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

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


def func(A, town):
    return A[town]

att = 1

visited = [1]
loopend = 0
loopstart = 0
if K > N:
    for i in range(K):
        att = func(A, att-1)
        if att in visited:
            loopstart = visited.index(att)
            break
        else:
            visited.append(att)
    loop = visited[loopstart:] # 周回する街
    rem = (K - loopstart) % len(loop)
    att = loop[rem]
else:
    for _ in range(K):
        att = func(A, att-1)

print(att)

### FIXED CODE ###

import sys

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

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


def func(A, town):
    return A[town]

att = 1

visited = set([1])
loopend = 0
loopstart = 0
if K > N:
    for i in range(N):
        att = func(A, att-1)
        #print(visited)
        if att in visited:
            visited = list(visited)
            loopstart = visited.index(att)
            break
        else:
            visited.add(att)
    loop = visited[loopstart:] # 周回する街
    rem = (K - loopstart) % len(loop)
    att = loop[rem]
else:
    for _ in range(K):
        att = func(A, att-1)

print(att)
### BUGGY CODE ###

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    H,W=map(int,readline().split())
    grid=[]
    for i in range(H):
        S=readline().strip()
        grid.append(S)
    up=[[0]*W for _ in range(H)]
    down=[[0]*W for _ in range(H)]
    left=[[0]*W for _ in range(H)]
    right=[[0]*W for _ in range(H)]

    #up,left
    for i in range(H):
        for j in range(W):
            if grid[i][j]==".":
                if i==0:
                    up[i][j]=1
                else:
                    up[i][j]=up[i-1][j]+1
            
                if j==0:
                    left[i][j]=1
                else:
                    left[i][j]=left[i][j-1]+1

    #down,right
    for i in range(H-1,-1,-1):
        for j in range(W-1,-1,-1):
            if grid[i][j]==".":
                if i==H-1:
                    down[i][j]=1
                else:
                    down[i][j]=down[i+1][j]+1

                if j==W-1:
                    right[i][j]=1
                else:
                    right[i][j]=right[i][j+1]+1

    res=0
    for i in range(H):
        for j in range(W):
            if grid[i][j]==".":
                res=max(res,up[i][j]+down[i][j]+left[i][j]+right[i][j]-3)
    
    print(res)
if __name__=="__main__":
    main()

### FIXED CODE ###

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    H,W=map(int,readline().split())
    grid=[]
    for i in range(H):
        S=readline().strip()
        grid.append(S)
    up=[[0]*W for _ in range(H)]
    down=[[0]*W for _ in range(H)]
    left=[[0]*W for _ in range(H)]
    right=[[0]*W for _ in range(H)]

    #up,left
    for i in range(H):
        for j in range(W):
            if grid[i][j]==".":
                if i==0:
                    up[i][j]=1
                else:
                    up[i][j]=up[i-1][j]+1
            
                if j==0:
                    left[i][j]=1
                else:
                    left[i][j]=left[i][j-1]+1

    #down,right
    for i in range(H-1,-1,-1):
        for j in range(W-1,-1,-1):
            if grid[i][j]==".":
                if i==H-1:
                    down[i][j]=1
                else:
                    down[i][j]=down[i+1][j]+1

                if j==W-1:
                    right[i][j]=1
                else:
                    right[i][j]=right[i][j+1]+1

    res=0
    for i in range(H):
        for j in range(W):
            if grid[i][j]==".":
                res=max(res,up[i][j]+down[i][j]+left[i][j]+right[i][j]-3)
    
    print(res)
if __name__=="__main__":
    main()
### BUGGY CODE ###

n, q = map(int,input().split())
S = input()
for i in range(q):
  l, r = map(int,input().split())
  cnt = S[l-1:r].count("AC")
  print(cnt)


### FIXED CODE ###

n,q = map(int,input().split())
s = list(input())

#a[i]:s[0]~s[i]までに何個ACがあったか
a = [0]*n
#end[i]:s[i]がACの'C'か
end = [False]*n
for i in range(1,n):
    if s[i] == 'C' and s[i-1] == 'A':
        a[i] = a[i-1]+1
        end[i] = True
    else:
        a[i] = a[i-1]
for i in range(q):
    L,R = map(int,input().split())
    L,R = L-1,R-1
    if L == 0:
        print(a[R])
    else:
        if end[L]:
            print(a[R]-a[L-1]-1)
        else:
            print(a[R]-a[L-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n, q = [int(i) for i in input().split()]
a1 = {}
a2 = {}
for _ in range(n - 1):
    x, y = [int(i) - 1 for i in input().split()]
    if x in a1:
        a1[x].append(y)
    else:
        a1[x] = [y]
    if y in a2:
        a2[y].append(x)
    else:
        a2[y] = [x]
root = [-1] * n

def c(ind=0, ro=0):
    global root
    if root[ind] != -1:
        return 0
    root[ind] = ro
    if ind in a1:
        for i in a1[ind]:
            if i!=0:
                c(i, ind)
    if ind in a2:
        for i in a2[ind]:
            if i!=0:
                c(i, ind)


c()
p = [0] * n
for _ in range(q):
    x, y = [int(i) for i in input().split()]
    p[x - 1] += y
r = []
for i in range(n):
    j = i
    k = 0
    while True:
        k += p[j]
        if j == 0 and root[j]==0:
            break
        j = root[j]
    r.append(str(k))
print(" ".join(r))


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)


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


n, q = [int(i) for i in input().split()]
ab = [[] for _ in range(n)]
for _ in range(n - 1):
    i, j = [int(i)-1 for i in input().split()]
    ab[i].append(j)
    ab[j].append(i)
p = [0]*n
for _ in range(q):
    i, j = [int(i) for i in input().split()]
    p[i-1] += j

al = [False]*n
pp = [0]*n


def a(i=0, j=0):
    al[i] = True
    j += p[i]
    pp[i] = str(j)
    for k in ab[i]:
        if not al[k]:
            a(k, j)


a()
print(" ".join(pp))
### BUGGY CODE ###

import sys
input=sys.stdin.readline

an,bn,cn,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
ans=[0]*k
mn=0
bmx=max(b)
cmx=max(c)
for ak in a:
    if ak+bmx+cmx<mn:break
    for bk in b:
        if ak+bk+cmx<mn:break
        for ck in c:
            abc=ak+bk+ck
            if abc<mn:break
            if abc>mn:
                if len(ans)==k:
                    ans.remove(mn)
                ans+=[abc]
                mn=min(ans)
for x in sorted(ans,reverse=True):
    print(x)


### FIXED CODE ###

an, bn, cn, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
la = len(a)
lb = len(b)
lc = len(c)

ans = [a[0] + b[0] + c[0]]
hq = [[a[0] + b[0] + c[0], 0, 0, 0]]
sumi = [[0, 0, 0]]
for _ in range(k - 1):
    mx = hq[0][0]
    ai = hq[0][1]
    bi = hq[0][2]
    ci = hq[0][3]
    hq = hq[1:]
    if ai + 1 < la and [ai + 1, bi, ci] not in sumi:
        hq += [[mx - a[ai] + a[ai + 1], ai + 1, bi, ci]]
        sumi += [[ai + 1, bi, ci]]
    if bi + 1 < lb and [ai, bi + 1, ci] not in sumi:
        hq += [[mx - b[bi] + b[bi + 1], ai, bi + 1, ci]]
        sumi += [[ai, bi + 1, ci]]
    if ci + 1 < lc and [ai, bi, ci + 1] not in sumi:
        hq += [[mx - c[ci] + c[ci + 1], ai, bi, ci + 1]]
        sumi += [[ai, bi, ci + 1]]
    hq.sort(reverse=True)
    ans += [hq[0][0]]

print(*ans,sep="\n")
### BUGGY CODE ###

import numpy as np

n, w = list(map(int, input().split()))
wv = np.array([list(map(int, input().split())) for i in range(n)])

dp = np.zeros((w + 1, n), dtype=np.int)
dp[wv[0, 0]:, 0] = np.full(dp[wv[0, 0]:, 0].shape, wv[0, 1])
for i in range(1, n):
    dp[:, i] = dp[:, i - 1]
    wNew, vNew = wv[i, 0], wv[i, 1]
    dp[wNew:, :] = np.fmax(dp[wNew:, :], vNew + dp[:-wNew, :])

print(dp[w, n - 1])


### FIXED CODE ###

import numpy as np


def main():
    N, W = list(map(int, input().split(' ')))
    items = np.array([list(map(int, input().split(' '))) for _ in range(N)])
    dp = np.zeros((N, W + 1))
    dp[0, items[0, 0]:] = items[0, 1]
    for n in range(1, N):
        weight, value = items[n, 0], items[n, 1]
        dp[n, :] = dp[n - 1, :]
        dp[n, weight:] = np.fmax(
            dp[n, weight:],
            value + dp[n - 1, :(- weight)]
        )
    print(int(dp[N - 1, W]))


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

n, s = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
dp = [0]*(s+1)
dp[0] = pow(2, n, MOD)
inv_2 = pow(2, MOD-2, MOD)
for a in A:
    for j in reversed(range(s+1)):
        if s < j+a:
            continue
        dp[j+a] += dp[j]*inv_2 % MOD

print(dp[-1] % MOD)

### FIXED CODE ###

n, s = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
W_MAX = s
dp = [0]*(W_MAX+1)
dp[0] = 1
inv_2 = pow(2, MOD-2, MOD)
for a in A:
    for j in reversed(range(W_MAX+1)):
        if W_MAX < j+a:
            continue
        dp[j+a] += dp[j]*inv_2
        dp[j+a] %= MOD

print(dp[-1]*pow(2, n, MOD) % MOD)
### BUGGY CODE ###

N,M = (int(x) for x in input().split())
S_arr = [int(x) for x in input().split()]
T_arr = [int(x) for x in input().split()]

dp = [[1]*(M+1) for _ in range(N+1)]

mod = 1000000007
for n in range(N):
    for m in range(M):
        if S_arr[n] == T_arr[m]:
            dp[n+1][m+1] = (dp[n+1][m]+dp[n][m+1]) % mod
        else:
            dp[n+1][m+1] = (dp[n+1][m]+dp[n][m+1]-dp[n][m]) % mod
print(dp[N][M])


### FIXED CODE ###

N,M = (int(x) for x in input().split())
S_arr = [int(x) for x in input().split()]
T_arr = [int(x) for x in input().split()]

dp = [[1]*(M+1) for _ in range(N+1)]

mod = 1000000007
for n in range(N):
    for m in range(M):
        if S_arr[n] == T_arr[m]:
            dp[n+1][m+1] = (dp[n+1][m]+dp[n][m+1]) % mod
        else:
            dp[n+1][m+1] = (dp[n+1][m]+dp[n][m+1]-dp[n][m]) % mod
print(dp[N][M])
### BUGGY CODE ###

Tmp = []
Tmp  = input().rstrip().split(' ')

N = int(Tmp[0])
K = int(Tmp[1])

Ans = 0
Num = K + 1
nTmp = 0
nTmp2 = 0

if K == 0:
    Ans = N**2
else:
    nTmp = int((N - K)*(N - K + 1)/2)
    Ans += nTmp
    while Num < N:
        nTmp2 = N
        while nTmp2 - K >= Num:
            nTmp = nTmp2 % Num
            if nTmp >= K:
                Ans += 1
            
            nTmp2 -= 1
        
        Num += 1


print(Ans)


### FIXED CODE ###

Tmp = []
Tmp  = input().rstrip().split(' ')

N = int(Tmp[0])
K = int(Tmp[1])

Ans = 0
nTmp = 0
nTmp2 = 0
nTmp3 = 0

if K == 0:
  Ans = N **2
else:
    for i in range(N+1):
        if i == 0:
            continue
        B = i
        nTmp = B - K
        if nTmp > 0:
            nTmp2 = N // B
            nTmp3 = (B - K) * nTmp2
            Ans += nTmp3
            nTmp2 = N % B
            if nTmp2 != 0:
                nTmp2 = nTmp2 - K + 1
                if nTmp2 > 0:
                    Ans += nTmp2
    
print(Ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
ans = sum(A)
for i in range(Q):
  b,c = map(int, input().split())
  cnt = A.count(b)
  for i in range(cnt):
    A.remove(b)
    A.append(c)
  ans += (c-b) * cnt
  print(ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
ans = sum(A)
C = Counter(A)

for i in range(Q):
  b, c = map(int, input().split())
  if C[b] != 0:
    cnt = C[b]
    C[c] += cnt
    C[b] = 0
    ans += (c-b) * cnt
  print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for i in range(q):
	l, r = map(int, input().split())
	x = s[l-1:r]
	ans = x.count("AC")
	print (ans)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
a = [list(map(int, input().split())) for _ in range(q)]

b = [0] * n
cnt = 0
for i in range(n-1):
	if s[i:i+2] == "AC":
		b[i+1] = b[i] + 1
	else:
		b[i+1] = b[i]
for i in a:
	print (b[i[1]-1] - b[i[0]-1])
### BUGGY CODE ###

import sys
N, M = map(int,input().split())
X = list(map(int,input().split()))
X.sort()

X_list = []
for i in range (len(X)-1):
    X_list.append(X[i+1]-X[i])

if M-N < 1:
    print(0)
    sys.exit()

for _ in range(N-1):
    X_list.remove(max(X_list))
    
print(sum(X_list))

### FIXED CODE ###

import numpy as np
import sys
N, M = map(int,input().split())
X = list(map(int,input().split()))
X.sort()

X_list = list(np.diff(X))

if M-N < 1:
    print(0)
    sys.exit()

X_list.sort(reverse=True)
print(sum(X_list[N-1:]))
### BUGGY CODE ###

n = int(input())
a = [[int(i) for i in input().split()] for i in range(n-1)]
q,k = (int(i) for i in input().split())
question = [[int(i) for i in input().split()] for i in range(q)]
x = []
for i in range(n):
	subx = []
	for j in range(n):
		subx.append(float("inf"))
	x.append(subx)
for i in range(n): x[i][i] = 0
for i in a: x[i[0]-1][i[1]-1],x[i[1]-1][i[0]-1] = i[2],i[2]
for p in range(n):
	for i in range(n):
		for j in range(n):
			x[i][j] = min(x[i][p]+x[p][j],x[i][j])
for i in question:
	print(x[i[0]-1][k-1]+x[k-1][i[1]-1])

### FIXED CODE ###

n = int(input())
a = [[int(i) for i in input().split()] for i in range(n-1)]
q,k = (int(i) for i in input().split())
question = [[int(i) for i in input().split()] for i in range(q)]
x,ans = [[] for i in range(n)],[False for i in range(n)]
for i in a:
	x[i[0]-1].append([i[1],i[2]])
	x[i[1]-1].append([i[0],i[2]])
visit = [False for i in range(n)]
visit[k-1],now = True,[k]
while now:
	p = now.pop()
	for i in x[p-1]:
		if not visit[i[0]-1]:
			visit[i[0]-1],ans[i[0]-1] = True,ans[p-1]+i[1]
			now.append(i[0])
for i in question:
	print(ans[i[0]-1]+ans[i[1]-1])
### BUGGY CODE ###

n=list(map(int,input().split()))
m=list(map(int,input().split()))
for i in range(n[1]):
  m.remove(max(m))
  if(len(m)==0):
    break
print(sum(m))


### FIXED CODE ###

n=list(map(int,input().split()))
m=list(map(int,input().split()))
m.sort()
if(n[0]<=n[1]):
  print(0)
else:
  print(sum(m[0:n[0]-n[1]]))
### BUGGY CODE ###

import numpy as np

N = int(input())

base = np.arange(1, N+1)
ans = np.sum(base)

for i in range(2, N+1):
	ans += np.sum(base[base%i == 0])

print(ans)

### FIXED CODE ###

import numpy as np

N = int(input())

ans = 0

for i in range(1, N+1):
	n = int(N/i)
	ans += n * (n + 1) / 2 * i

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

N, X, M = map(int, input().split())  # 数列の項数N, 数列の第一項X, modM
MOD = M
A = [X]
# 1~N+1のN項
for _ in range(N-1):
    A.append(A[-1]**2%MOD)
print(sum(A))


### FIXED CODE ###

# happendはsetで保持しておき，roopはlistで保持しておく
N, X, M = map(int, input().split())  # modMは10**5以下が与えられる
happend = set()
A = [X]
MOD = M
# 第1~N項まで計N項の和をもとめる
start = 0
for _ in range(N-1):
    if A[-1]**2 % MOD not in happend:
        happend.add(A[-1]**2 % MOD)
        A.append(A[-1]**2 % MOD)
    else:
        start = A.index(A[-1]**2 % MOD)
        break

roop_count = (N-start)//len(A[start:])

ans = sum(A[:start]) + sum(A[start:])*roop_count + sum(A[start:start+(N-start) % len(A[start:])])
# print(A[:start], A[start:], A[start:start+(N-start) % len(A[start:])])
print(ans)
### BUGGY CODE ###

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

from itertools import accumulate


def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [0]*(M+1)
    for s in S:
        *dp, = map(int.__add__, dp, accumulate(map(lambda d,t: (d+1 if s.__eq__(t) else 0), [0]+dp, T)))
    res = (dp[-1]+1)%(10**9+7)
    return str(res)

if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

# -*- coding: utf-8 -*-
def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [1]*(M+1)
    for s in S:
        is_s = s.__eq__
        dp_ = dp[:]
        acc = 0
        for i, t in enumerate(T):
            if is_s(t):
                acc += dp_[i]
            dp[i+1] = dp_[i+1] + acc
    res = (dp[-1])%(10**9+7)
    return str(res)

if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

S = input()
mod = 10**9+7

N = len(S)
A1,A2,A3,C1,C2,C3 = [1]*N,[1]*N,[1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    if S[i-1]=="?":
        aa += 1
        A3[i] = A3[i-1]*3
    else:
        A3[i] = A3[i-1]
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    if S[N-1-i+1]=="?":
        cc += 1
        C3[N-1-i] = C3[N-1-i+1]*3
    else:
        C3[N-1-i] = C3[N-1-i+1]
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i]=="B" or S[i]=="?":
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = A3[i]*A1[i] + A3[i]//3*A2[i]
            ta %= mod
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = C3[i]*C1[i] + C3[i]//3*C2[i]
            tc %= mod
        Ans += ta*tc
        Ans %= mod

print(Ans)

### FIXED CODE ###

S = input()
mod = 10**9+7

N = len(S)
A1,A2,C1,C2 = [1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    elif S[i-1]=="?":
        aa += 1
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    elif S[N-1-i+1]=="?":
        cc += 1
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i] in ("B","?"):
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = pow(3,A2[i],mod)*A1[i] + pow(3,A2[i]-1,mod)*A2[i]
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = pow(3,C2[i],mod)*C1[i] + pow(3,C2[i]-1,mod)*C2[i]
        Ans += ta*tc
        Ans %= mod

print(Ans)
### BUGGY CODE ###

import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

S = input()
S = S[::-1]

dp = [[0] * 13 for _ in range(len(S))]
mod = 10 ** 9 + 7

if S[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(S[0])] = 1

for i in range(1, len(S)):
    if S[i] == '?':
        for j in range(13):
            for k in range(10):
                dp[i][(j + 10 ** i * k) % 13] += dp[i-1][j]
                dp[i][(j + 10 ** i * k) % 13] %= mod
    else:
        for j in range(13):
            dp[i][(j + 10 ** i * int(S[i])) % 13] += dp[i-1][j]
            dp[i][(j + 10 ** i * int(S[i])) % 13] %= mod
print(dp[len(S) - 1][5])


### FIXED CODE ###

import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

S = input()

dp = [[0] * 13 for _ in range(len(S))]
mod = 10 ** 9 + 7

if S[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(S[0])] = 1

for i in range(1, len(S)):
    if S[i] == '?':
        for j in range(13):
            for k in range(10):
                dp[i][(j * 10 + k) % 13] += dp[i-1][j]
                dp[i][(j + 10 + k) % 13] %= mod
    else:
        for j in range(13):
            dp[i][(j * 10 + int(S[i])) % 13] += dp[i-1][j]
            dp[i][(j * 10 + int(S[i])) % 13] %= mod
print(dp[len(S) - 1][5])
### BUGGY CODE ###

S = str(input())
n = int(input())
Q = [list(map(str, input().split())) for _ in range(n)]
cnt = 0
for q in Q:
    if q[0] == "1":
        cnt += 1
    elif q[0] == "2":
        if (int(q[1])+cnt)%2 == 1:
            S = q[2] + S
        else:
            S = S + q[2]

if cnt%2==1:
    S = list(S)
    S.reverse()
print("".join(S))

### FIXED CODE ###

S = str(input())
n = int(input())
Q = [list(map(str, input().split())) for _ in range(n)]
cnt = 0
s_pre = ""
s_pro = ""
for q in Q:
    if q[0] == "1":
        cnt += 1
    else:
        if (int(q[1])+cnt)%2 == 1:
#             S = q[2] + S
            s_pre = q[2] + s_pre
        else:
            s_pro = s_pro + q[2]
#             S = S + q[2]

S = s_pre + S + s_pro
if cnt%2==1:
    S = list(S)
    S.reverse()
print("".join(S))
### BUGGY CODE ###

import sys
import numpy as np
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[-1] * 100010 for _ in range(110)]

def rec(i, j):
  if dp[i][j] != -1:
    return dp[i][j]
  if i == n:
    return 0
  if j < a[i][0]:
    res = rec(i+1, j)
  else:
    res = max(rec(i+1, j), rec(i+1, j - a[i][0]) + a[i][1])
  dp[i][j] = res
  return dp[i][j]

print(int(rec(0, w)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0] * (w+1) for _ in range(n+1)]

def rec(i, j):
  if dp[i][j] != 0:
    return dp[i][j]
  if i == n:
    res = 0
  elif j < a[i][0]:
    res = rec(i+1, j)
  else:
    res = max(rec(i+1, j), rec(i+1, j - a[i][0]) + a[i][1])
  dp[i][j] = res
  return dp[i][j]

print(int(rec(0, w)))
### BUGGY CODE ###

"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

    dp = [[[0]*4 for _ in range(C)] for _ in range(R)]
    dp[0][0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[i][j][0] = max(dp[i][j][0],max(dp[i-1][j]))
                if v:
                    dp[i][j][1] = max(dp[i][j][1],max(dp[i-1][j])+v)

            if j!=0:
                #左から入る場合のシミュレート
                dp[i][j][0] = max(dp[i][j][0],dp[i][j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1]+v,dp[i][j-1][k])
                else:
                    for k in range(1,4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
    print(max(dp[-1][-1]))
main()

### FIXED CODE ###

"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()