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

N, C = map(int, input().split())

D = [ [int(i) for i in input().split()] for _ in range(C) ] 
c = [ [int(i) for i in input().split()] for _ in range(N) ] 

costD = [0 for _ in range(C)]

for c0 in range(C):
    tmpD = [0] * 3
    for i in range(N):
        for j in range(N):
            tmpD[(i+j)%3] += D[c[i][j]-1][c0]
    costD[c0] = tmpD

kohoD = []

for c1 in range(C):
    for c2 in range(C):
        if c1 == c2:
            continue
        for c3 in range(C):
            if c1 == c3 or c2 == c3:
                continue
            kohoD += [(costD[c1][0] + costD[c2][1] + costD[c3][2])]

print(sorted(kohoD)[0])


### FIXED CODE ###

import itertools
 
 
def main():
    N, C = map(int, input().split())
    D = [list(map(int, input().split())) for _ in range(C)]
    CC = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
 
    cost = [[0 for _ in range(C)] for _ in range(3)]
    for c in range(C):
        for i in range(N):
            for j in range(N):
                cost[(i + j) % 3][c] += D[CC[i][j]][c]
 
    res = float("inf")
    color = [i for i in range(C)]
    for i, c in enumerate(list(itertools.permutations(color, 3))):
        tmp = 0
        for it in range(3):
            tmp += cost[it][c[it]]
        res = min(res, tmp)
 
    print(res)
 
main()
### BUGGY CODE ###

N = int(input())
ans = 0

for i in range(N):
    ans += i
print(ans)

### FIXED CODE ###

N = int(input())
print((N)*(N-1) //2)
### BUGGY CODE ###

import queue

N,M = map(int, input().split())
dst = [[] for i in range(N+1)]

for i in range(M):
  u,v = map(int, input().split())
  dst[u].append(v)
S,T = map(int, input().split())

dst2 = [[] for i in range(N+1)]

for i in range(1,N+1):
  for s0 in dst[i]:
    for s1 in dst[s0]:
      for s2 in dst[s1]:
        if i != s2:
          if not s2 in dst2[i]:
            dst2[i].append(s2)
  
def bfs(s):
  que = queue.Queue()
  que.put(s)
  d = [-1 for _ in range(N+1)]
  d[s] = 0

  while not que.empty():

    p = que.get()
    if (T == p):
      return d[p]

    for pp in dst2[p]:
      if d[pp] == -1:
        que.put(pp)
        d[pp] = d[p]+1

  return -1

ans = bfs(S)
print(ans)


### FIXED CODE ###

import collections

N,M = map(int, input().split())
G = [[] for i in range(3*N+1)]

for i in range(M):
  u,v = map(int, input().split())
  G[u].append(v+N)
  G[u+N].append(v+2*N)
  G[u+2*N].append(v)
S,T = map(int, input().split())

def bfs(s):
  que = collections.deque()
  que.append(s)
  d = [-1 for _ in range(3*N+1)]
  d[s] = 0

  while (0 < len(que)):

    p = que.popleft()
    if (T == p):
      return d[p]

    for pp in G[p]:
      if d[pp] == -1:
        que.append(pp)
        d[pp] = d[p]+1

  return -1

ans = bfs(S)
if (-1 == ans):
  print(-1)
else:
  print(ans//3)
### BUGGY CODE ###

def min(a, b):
    if a >= b:
        res = a - b
    elif a < b:
        res = b - a
    return res

n,k = map(int, input().split())
if n%k == 0:
    print(0)
    quit()

min_num = float('inf')
res_list = []
while(1):
    res = min(n, k)
    if res < min_num:
        min_num = res
    if res == 0:
        break
    if res in res_list:
        break
    n = res
    res_list.append(res)

print(min_num)


### FIXED CODE ###

def min(a, b):
    if a >= b:
        res = a - b
    elif a < b:
        res = b - a
    return res

n,k = map(int, input().split())
if n%k == 0:
    print(0)
    quit()
else:
    n = n%k

min_num = float('inf')
res_list = []
while(1):
    res = min(n, k)
    if res < min_num:
        min_num = res
    if res == 0:
        break
    if res in res_list:
        break
    n = res
    res_list.append(res)

print(min_num)
### BUGGY CODE ###

N, D, A=map(int, input().split())
XH=[list(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda x:x[0])
bomb_j=[0 for _ in range(N)]

for i in range(N):
  X=XH[i][0]
  left, right=0, N-1
  while left<=right:
    mid=(left+right)//2
    if XH[mid][0]>X+2*D:
      right=mid-1
    else:
      left=mid+1
  bomb_j[i]=left-1

ans, pos=0, 0
Hs=[H for X, H in XH]
while pos<N:
  attack=(Hs[i]-1)//A+1
  for i in range(pos, bomb_j[pos]+1):
    Hs[i]=max(0, Hs[i]-attack*A)
  while pos<N and Hs[pos]==0:
    pos+=1
  ans+=attack
print(ans)

### FIXED CODE ###

from collections import deque

N, D, A=map(int, input().split())
XH=[list(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda x:x[0])
total=0
q=deque()
ans=0

for i in range(N):
  X, H=XH[i]
  while len(q) and q[0][0]<X:
    total-=q.popleft()[1]
  H-=total
  if H>0:
    attack_cnt=(H-1)//A+1
    ans+=attack_cnt
    damage=attack_cnt*A
    total+=damage
    q.append([X+2*D, damage])
print(ans)
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
ls = sorted(map(int, input().split()))
ls2 = [list(map(int, input().split())) for _ in range(m)]
ls2.sort(key=lambda x: (x[1], x[0]), reverse=True)
left = 0
for b, c in ls2:
    i = bisect.bisect(ls[left:], c)
    i = min(i, b)
    for j in range(i):
        ls[left + j] = c
    left += i
print(sum(ls))

### FIXED CODE ###

n, m = map(int, input().split())
ls = sorted(map(int, input().split()))
ls2 = [list(map(int, input().split())) for _ in range(m)]
ls2.sort(key=lambda x: (x[1], x[0]), reverse=True)
left = 0
right = 0
index = 0
res = 0
while left < n:
    if index == len(ls2):
        break
    b, c = ls2[index]
    if c <= ls[left]:
        break
    right = left + 1
    while right <= n:
        if right == n:
            res += c * (right - left)
            break
        if ls[right] <= c and right - left < b:
            right += 1
        else:
            res += c * (right - left)
            break
    left = right
    index += 1

print(res + sum(ls[left:]))
### BUGGY CODE ###

from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    n = int(input())
    graph = [[] for _ in range(n+1)]

    A = [0]+list(map(int, input().split()))

    for i in range(n-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 1

    d = deque()
    d.append((1, [0, A[1]]))

    while d:
        v, dp = d.popleft()
        graph2=[]
        for i in graph[v]:
            if dist[i] == -1:
                graph2.append(i)
        for index, i in enumerate(graph2,1):
            if index==len(graph2):
                if dp[-1] < A[i]:
                    dp.append(A[i])
                else:
                    bis = bisect.bisect_left(dp, A[i])
                    dp[bis] = A[i]
                dist[i] = len(dp)-1
                d.append((i, dp))
            else:
                ndp=dp.copy()
                if dp[-1] < A[i]:
                    ndp.append(A[i])
                else:
                    bis = bisect.bisect_left(ndp, A[i])
                    ndp[bis] = A[i]
                dist[i] = len(ndp)-1
                d.append((i, ndp))

    print(*dist[1:], sep="\n")

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")
### BUGGY CODE ###

n, k, q = map(int, input().split())
A = [int(input()) for _ in range(q)]
P = [k for _ in range(n)]

for i in range(q):
    for j in range(n):
        if (A[i] - 1) != j:
            P[j] -= 1

for i in range(n):
    print("Yes" if P[i] > 0 else "No")

### FIXED CODE ###

n, k, q = map(int, input().split())
A = [int(input()) for _ in range(q)]
P = [k - q] * n

for i in range(q):
    P[A[i] - 1] += 1

for i in range(n):
    print("Yes" if P[i] > 0 else "No")
### BUGGY CODE ###

N, M = map(int, input().split())
seki = set(list(range(1,N+1)))
for i in range(M):
    l, r = map(int, input().split())
    seki &= set(list(range(l, r+1)))
print(len(seki))

### FIXED CODE ###

# 解説を見ての解答
from sys import stdin

n, m = map(int, stdin.readline().rstrip().split())
lr = [list(map(int, stdin.readline().rstrip().split())) for i in range(m)]

l, r = lr[0][0], lr[0][1]
for i in range(m):
    l = max(l, lr[i][0])
    r = min(r, lr[i][1])

print(max(0,r-l+1))
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
l.append(99999999)
c = 0
for i in range(n - 2):
    t = i + 2
    for j in range(i + 1, n - 1):
        for k in range(t, n + 1):
            if l[i] + l[j] <= l[k]:
                t = k
                break
        if t > j: c += t - j - 1
        if j + 1 == t: t += 1
print(c)

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n = int(input())
  l = list(map(int, input().split()))
  l.sort()
  l.append(99999999)
  c = 0
  for i in range(n - 2):
      t = i + 2
      for j in range(i + 1, n - 1):
          for k in range(t, n + 1):
              if l[i] + l[j] <= l[k]:
                  t = k
                  break
          if t > j: c += t - j - 1
          if j + 1 == t: t += 1
  print(c)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
h.insert(0, -1)
INF = 100100100100
dp_table = [INF]*(N+1)
dp_table[0] = -1
dp_table[1] = 0

for i in range(2, N+1): # 各足場i(2~N)を緩和.
  for k in range(1,K+1): # 各足場i(2~N)について高々K通りの遷移.
    if i-k <=0: break #足場i-kからの遷移をみるが足場の最小は1. だから, 0以下になったらbreak.
    dp_table[i] = min(dp_table[i], dp_table[i-k] + abs(h[i]-h[i-k]))
print(dp_table[N])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
h.insert(0, -1)
INF = 100100100100
dp_table = [INF]*(N+1)
dp_table[0] = -1
dp_table[1] = 0

for i in range(2, N+1): # 各足場i(2~N)を緩和.
  for k in range(1,K+1): # 各足場i(2~N)について高々K通りの遷移.
    if i-k <=0: break #足場i-kからの遷移をみるが足場の最小は1. だから, 0以下になったらbreak.
    dp_table[i] = min(dp_table[i], dp_table[i-k] + abs(h[i]-h[i-k]))
print(dp_table[N])
### 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
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            q.append(i*W+k)
            saitan[i*W+k] = 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)] <= 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=int(input())
a=[]
for i in range(n):
    a.append(int(input())-1)
ans=1
i=0
b=[]
while(1):
    if a[i]==1:
        print(ans)
        exit()
    elif i in b:
        print(-1)
        exit()
    else:
        b.append(i)
        i=a[i]
        ans+=1

### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(int(input())-1)
ans=1
i=0
b=[]
while(1):
    if ans==n:
        print(-1)
        exit()
    elif a[i]==1:
        print(ans)
        exit()
    else:
        ans+=1
        i=a[i]
### BUGGY CODE ###

k, s = list(map(int, input().split()))
cnt = 0
for x in range(k + 1):
    for y in range(k + 1):
        for z in range(k + 1):
            if s == x + y + z:
                cnt += 1
print(cnt)


### FIXED CODE ###

k, s = list(map(int, input().split()))
count = 0
for i in range(0, k + 1):  # X value
    for j in range(0, k + 1):  # Y value
        if 0 <= s - i - j <= k:  # s - i - j = Z
            count += 1
print(count)
### BUGGY CODE ###

def main():
    n = int(input())
    aa = [int(input()) - 1 for _ in range(n)]
    i = 0
    res = 0
    while True:
        if aa[i] == 1:
            print(res + 1)
            break
        if aa[i] == 0:
            print(-1)
            break
        i = aa[i]
        res += 1


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    aa = [int(input()) - 1 for _ in range(n)]
    visiteds = [False] * n
    i = 0
    res = 0
    while True:
        if visiteds[i]:
            print(-1)
            break
        if i == 1:
            print(res)
            break
        visiteds[i] = True
        res += 1
        i = aa[i]


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

n = int(input())
ans = 1
an = list(map(int,input().split()))
for i in an:
    if i == 0:
        ans = 0
if ans != 0:
    for i in range(n):
        ans = ans * an[i]
        if ans > 10**18:
            ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
ans = 1
an = list(map(int,input().split()))
for i in an:
    if i == 0:
        ans = 0
if ans != 0:
    for i in range(n):
        ans = ans * an[i]
        if ans > 10**18:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

import math
if __name__ == "__main__": 
	string = input()
	l = string.split(" ")
	a = int(l[0])
	b = int(l[1])
	n = int(l[2])
	ans = 0
	for i in range(1,n+1):
		f = math.floor((a*i)/b)
		s = math.floor(i/b)
		temp = int(f) - (a*int(s))
		if(temp > ans):
			ans = temp
	print(ans)

### FIXED CODE ###

import math
if __name__ == "__main__": 
	string = input()
	l = string.split(" ")
	a = int(l[0])
	b = int(l[1])
	n = int(l[2])
	ans = 0
	ni = min(n,b-1)
	f = math.floor((a*(ni))/b)
	s = math.floor((ni)/b)
	temp = int(f) - (a*int(s))
	ans = temp
	# if(n>b):
	# 	f = math.floor((a*(b-1))/b)
	# 	s = math.floor((b-1)/b)
	# 	temp = int(f) - (a*int(s))
	# 	ans = temp
	# else:
	# 	f = math.floor((a*(n))/b)
	# 	s = math.floor((n)/b)
	# 	temp = int(f) - (a*int(s))
	# 	ans = temp
	print(ans)
### BUGGY CODE ###

def sol(x):
  num = P
  cnt = 0
  while cnt<N:
    if cnt!=N-1:
      if num%(x**2)!=0:return False
      else:num/=x**2
      cnt+=2
    else:
      if num%x!=0:return False
      else:num/=x
      cnt += 1
  return True
  

N,P=map(int,input().split())
for x in range(int(P**(1/N))+1,0,-1):
  if sol(x):
    print(x)
    exit()


### FIXED CODE ###

def primes(n):
  ps = {}
  while n%2==0:
    n//=2
    if 2 not in ps:
      ps[2] = 1
    else:
      ps[2] += 1
  
  for i in range(3,int(n**.5)+1,2):
    while n%i==0:
      n//=i
      if i not in ps:
        ps[i] = 1
      else:
        ps[i] += 1
  
  if n!=1:
    ps[n] = 1
  
  return ps
  
N,P = map(int,input().split())
if N==1:
  print(P)
  exit()
ps = primes(P)
ans = 1
for p, num in ps.items():
  if num>=N:
    ans *= p**(num//N)
print(ans)
### BUGGY CODE ###

n=int(input())
s=[input() for i in range(n)]
dic={}
for word in s:
    if word in dic:
        dic[word]+=1
    else:
        dic[word]=1
for key,value in sorted(dic.items()):
    if value==max(dic.values()):
        print(key)

### FIXED CODE ###

N=int(input())
S=[input() for i in range(N)]
dictionary={}
for word in S:
    if word in dictionary:
        dictionary[word]+=1
    else:
        dictionary[word]=1
maximum=max(dictionary.values())
for key,value in sorted(dictionary.items()):
    if value==maximum:
        print(key)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100002)


N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')] * N
dp[0] = 0


def rec(i):

    if dp[i] < float('inf'):
        return dp[i]

    res = float('inf')
    for j in range(1, K+1):
        if i >= j:
            res = min(res, rec(i - j) + abs(h[i] - h[i - j]))

    dp[i] = res
    return res


print(rec(N-1))

### FIXED CODE ###

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

dp = [float('inf') for _ in range(N)]
dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        if i - j >= 0:
            if dp[i - j] + abs(h[i] - h[i - j]) < dp[i]:
                dp[i] = dp[i - j] + abs(h[i] - h[i - j])
print(dp[N-1])
### BUGGY CODE ###

n,m,d = map(int, input().split())
ans = (n-d)*2 * n**(m-2) * (m-1) / (n**m)
if d == 0:
    ans /= 2
print(ans)

### FIXED CODE ###

n,m,d = map(int, input().split())
ans = (n-d)*2  * (m-1) / (n**2)
if d == 0:
    ans /= 2
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
s=' '+input().rstrip()
t=' '+input().rstrip()
dp=[['']*len(t) for i in range(len(s))]
for i in range(1,len(s)):
    for j in range(1,len(t)):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+s[i]
        else:
            if len(dp[i-1][j])>len(dp[i][j-1]):
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=dp[i][j-1]
print(dp[len(s)-1][len(t)-1])








### FIXED CODE ###

import sys
input=sys.stdin.readline
s=' '+input().rstrip()
t=' '+input().rstrip()
m=len(s)-1
n=len(t)-1
dp=[[0]*(n+1) for i in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ans=''
while m>0 and n>0:
    if dp[m][n]==dp[m][n-1]:
        n-=1
    elif dp[m][n]==dp[m-1][n]:
        m-=1
    elif dp[m][n]==dp[m-1][n-1]+1:
        ans=s[m]+ans
        m-=1
        n-=1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1
for i in range(N):
    ans *= A[i]
if(ans > 10**18):
    print(-1)
    exit()
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1
for i in range(N):
    if(A[i]==0):
        print(0)
        exit()
for i in range(N):
    ans *= A[i]
    if(ans > 10**18):
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

terms = [int(i) for i in input().split(" ")]
scores = [int(i) for i in input().split(" ")]

N = terms[0]
K = terms[1]

tempScore = []
scoreSet = []

for i in range(N-K+1):
    for j in range(K):
        tempScore.append(scores[j+i])
    scoreSet.append(tempScore)
    tempScore = []

for i in range(len(scoreSet)-1):
    if scoreSet[i][0] < scoreSet[i+1][K-1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

terms = [int(i) for i in input().split(" ")]
scores = [int(i) for i in input().split(" ")]

N = terms[0]
K = terms[1]

tempScore = []
scoreSet = []

for i in range(N-K):
    if scores[i] < scores[i+K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

R,C,K = map(int,input().split())
mat = [ [0]*C for _ in range(R) ]
for _ in range(K):
  r,c,v = map(int,input().split())
  mat[r-1][c-1] = v

# dp[i][j][k] = i,jまでで、i列のものをk個取ったときのスコア
dp0 = [[0] * (C+1) for _ in range(R+1) ]
dp1 = [[0] * (C+1) for _ in range(R+1) ]
dp2 = [[0] * (C+1) for _ in range(R+1) ]
dp3 = [[0] * (C+1) for _ in range(R+1) ]

for i in range(1,R+1):
  for j in range(1,C+1):
    m = mat[i-1][j-1]
    # 左からの遷移
    dp1[i][j] = max(dp1[i][j-1], dp0[i][j-1]+m)
    dp2[i][j] = max(dp2[i][j-1], dp1[i][j-1]+m)
    dp3[i][j] = max(dp3[i][j-1], dp2[i][j-1]+m)

    # 上からの遷移
    x = max(dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])
    dp0[i][j] = max(dp0[i][j-1], x)
    dp1[i][j] = max(dp1[i][j], x+m)

print(max(dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C]))

### FIXED CODE ###

R,C,K = map(int,input().split())
mat = {}
for _ in range(K):
  r,c,v = map(int,input().split())
  mat[(r,c)] = v

# dp[i][j][k] = i,jまでで、i列のものをk個取ったときのスコア
dp0 = [[0] * (C+1) for _ in range(R+1) ]
dp1 = [[0] * (C+1) for _ in range(R+1) ]
dp2 = [[0] * (C+1) for _ in range(R+1) ]
dp3 = [[0] * (C+1) for _ in range(R+1) ]

for i in range(1,R+1):
  for j in range(1,C+1):
    if (i,j) in mat:
      m = mat[(i,j)]
      # 左からの遷移
      dp1[i][j] = max(dp1[i][j-1], dp0[i][j-1]+m)
      dp2[i][j] = max(dp2[i][j-1], dp1[i][j-1]+m)
      dp3[i][j] = max(dp3[i][j-1], dp2[i][j-1]+m)
    else:
      dp1[i][j] = dp1[i][j-1]
      dp2[i][j] = dp2[i][j-1]
      dp3[i][j] = dp3[i][j-1]

    # 上からの遷移
    x = max(dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])
    dp0[i][j] = max(dp0[i][j-1], x)
    if (i,j) in mat:
      m = mat[(i,j)]
      dp1[i][j] = max(dp1[i][j], x+m)
    else:
      dp1[i][j] = max(dp1[i][j], x)

print(max(dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C]))
### BUGGY CODE ###

MOD = 10 ** 9 + 7

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

perm = [0] * (10**5)
perm[0] = 1
for l in range(1,10 ** 5):
    perm[l] = (perm[l-1] * (K-l-1)) % MOD

info = [[] for _ in range(N)]

def intminus(t):
    return int(t)-1

for i in range(N-1):
    a,b = map(intminus,input().split())
    info[a].append(b)
    info[b].append(a)

count = 1

for j in range(1+len(info[0])):
    count = (count * (K-j)) % MOD

stack = info[0][:]
visited = [0] * N
visited[0] = 1

while stack:
    x = stack.pop(-1)
    if visited[x] == 1:
        continue
    count = (count * perm[len(info[x])-1]) % MOD
    stack = stack + info[x]
    visited[x] = 1
    #print(stack,count)

print(count)

### FIXED CODE ###

MOD = 10 ** 9 + 7

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

perm = [0] * (10**5)
perm[0] = 1
for l in range(1,10 ** 5):
    perm[l] = (perm[l-1] * (K-l-1)) % MOD

info = [[] for _ in range(N)]

def intminus(t):
    return int(t)-1

for i in range(N-1):
    a,b = map(intminus,input().split())
    info[a].append(b)
    info[b].append(a)

count = 1

for j in range(1+len(info[0])):
    count = (count * (K-j)) % MOD

stack = []
for p in info[0]:
    stack.append([0,p])

while stack:
    x = stack.pop(-1)
    count = (count * perm[len(info[x[1]])-1]) % MOD
    for xx in info[x[1]]:
        if xx == x[0]:continue
        stack.append([x[1],xx])

print(count)