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

#!/usr/bin/env python3
import sys

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


n, k = MI()
p = list(MI())
c = list(MI())

p.insert(0, 0)
c.insert(0, 0)

ans = -float("INF")
for i in range(1, n + 1):
    next = p[i]
    loop_score = 0
    score = 0
    MAX = -float("INF")

    for j in range(1, k + 1):
        score += c[next]
        MAX = max(MAX, score)
        if next == i:
            loop_score = score
            loop_size = j
            if loop_score > 0:
                q, r = divmod(k, loop_size)
                # 周れるだけ周る-1+余りの回数で最大となるマス動く
                score1 = loop_score * (q - 1) + MAX
                # 周れるだけ周る+余りの回数で最大となるマス動くとき
                score2 = loop_score * q
                MAX = score2
                next = p[i]
                for _ in range(1, r + 1):
                    score2 += c[next]
                    MAX = max(MAX, score2)
                    next = p[next]
                score = max(score1, score2)
                break
            else:
                # 一周未満
                score = MAX
                break
        else:
            next = p[next]
    ans = max(ans, score)


print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


n, k = MI()
p = list(MI())
c = list(MI())

p.insert(0, 0)
c.insert(0, 0)

ans = -float("INF")
for i in range(1, n + 1):
    next = p[i]
    score = 0
    MAX = -float("INF")

    for j in range(1, k + 1):
        score += c[next]
        MAX = max(MAX, score)
        if next == i:
            loop_score = score
            loop_size = j
            if loop_score > 0:
                q, r = divmod(k, loop_size)
                # 周れるだけ周る-1+余りの回数で最大となるマス動く
                score1 = loop_score * (q - 1) + MAX
                # 周れるだけ周る+余りの回数で最大となるマス動くとき
                score2 = loop_score * q
                MAX = score2
                next = p[i]
                for _ in range(1, r + 1):
                    score2 += c[next]
                    MAX = max(MAX, score2)
                    next = p[next]
                score = max(score1, MAX)
                break
            else:
                # 一周未満
                score = MAX
                break
        else:
            next = p[next]
    else:
        score = MAX

    ans = max(ans, score)


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

s = str(input())

l = [1 if c == "<" else -1 for c in list(s)]

def leftmore(i):
    num = 0
    while True:
        if i == 0:
            break
        elif s[i-1] == "<":
            i -= 1
            num += 1
        else:
            break
    return num

def rightless(i):
    num = 0
    while True:
        if i == len(s):
            break
        elif s[i] == ">":
            i += 1
            num += 1
        else:
            break
    return num

sumlist = [0] * (len(s)+1)
for i in range(len(sumlist)):
    sumlist[i] = max(leftmore(i),rightless(i))


print(sum(sumlist))

### FIXED CODE ###

s = str(input())
#s = "<>>><<><<<<<>>><"
ans = 0
def leftmore(ln):
    ret = [0]
    cur = 0
    for c in ln:
        if c == "<":
            cur += 1
        else:
            cur = 0
        
        ret.append(cur)
    return ret

def rightless(ln):
    revl = reversed(ln)
    ret = [0]
    cur = 0
    for c in revl:
        if c == ">":
            cur += 1
        else:
            cur = 0
        ret.append(cur)
    return list(reversed(ret))

lm = leftmore(s)
rl = rightless(s)
for i in range(len(s)+1):
    ans += max(lm[i],rl[i])
print(ans)
### BUGGY CODE ###

from collections import Counter
s = input()
ls = []
for i in range(1, len(s)+1):
    ls.append(int(s[len(s)-i:]))

arr = [0 for i in range(len(s)+1)]
for i in range(len(s)):
    arr[i+1] = ls[i]%2019

def comb(a):
    return a*(a-1)//2

m = Counter(arr)
ans = 0
for x, y in m.items():
    ans += comb(y)
print(ans)

### FIXED CODE ###

from collections import Counter, defaultdict
a = defaultdict(int)
a[0] += 1
s = input()[::-1]
cur = 0
for i, x in enumerate(s):
    cur += (int(x)*pow(10, i, 2019))%2019
    cur %= 2019
    a[cur] += 1

def comb(a):
    return a*(a-1)//2

ans = 0
for x in a.values():
    if x >= 2:
        ans += comb(x)
print(ans)
### BUGGY CODE ###

s = 'AKIHABARA'
t = raw_input()
n = len(t)
i = 0
j = 0
while i < n and j < len(s): 
	if t[i] == s[j]:
		i += 1
		j += 1
	elif s[j] == 'A':
		j += 1
	else:
		print 'NO'
		exit()
while j < len(s):
	if s[j] == 'A':
		j += 1
if i == n and j == len(s):
	print 'YES'
else:
	print 'NO'
	



### FIXED CODE ###

s = 'AKIHABARA'
t = raw_input()
n = len(t)
i = 0
j = 0
while i < n and j < len(s): 
	if t[i] == s[j]:
		i += 1
		j += 1
	elif s[j] == 'A':
		j += 1
	else:
		print 'NO'
		exit()
while j < len(s):
	if s[j] == 'A':
		j += 1
	else:
		break
if i == n and j == len(s):
	print 'YES'
else:
	print 'NO'
### BUGGY CODE ###

# N体の敵、K回の必殺技
N, K = map(int, input().strip().split(' '))
N_list = list(map(int, input().strip().split(' ')))
sorted_N = sorted(N_list, reverse=True)

# 必殺技で体力が多い敵からヤる
for i in range(K):
  sorted_N.pop(0)
  if sorted_N == []:
    break

if sorted_N ==[]:
  print(0)
else:
  print(sum(sorted_N))

### FIXED CODE ###

# N体の敵、K回の必殺技
N, K = map(int, input().strip().split(' '))
N_list = list(map(int, input().strip().split(' ')))
sorted_N = sorted(N_list, reverse=True)

# 必殺技で体力が多い敵からヤる
del sorted_N[:K]

if sorted_N ==[]:
  print(0)
else:
  print(sum(sorted_N))
### BUGGY CODE ###

mod=10**9+7
ferumaC=300000
fac=[0 for i in range(ferumaC)]
fac[0]=1
ifac=[0 for i in range(ferumaC)]
ifac[0]=1
def mpow(x,n):
    num=1
    while n > 0:
        if n&1:
            num=num*x%mod
        x=x*x%mod
        n=n>>1
    return(num)

for i in range(0,ferumaC-1):
    fac[i+1]=(fac[i]*(i+1))%mod
    ifac[i+1]=ifac[i]*mpow(i+1,mod-2)%mod
def comb(a,b):
    if a==0 and b==0:return(1)
    if a<b or a<0:return(0)
    tmp=ifac[a-b]*ifac[b]%mod
    return(tmp*fac[a]%mod)


from fractions import gcd
def lcm(a,b):
    return(a*b//gcd(a,b))

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

value=A[0]
for i in range(1,N):
    value=lcm(value,A[i])
count=0
for a in A:
    count+=value*(mpow(a,mod-2))
    count%=mod
print(count)


### FIXED CODE ###

mod=10**9+7
ferumaC=300000
fac=[0 for i in range(ferumaC)]
fac[0]=1
ifac=[0 for i in range(ferumaC)]
ifac[0]=1
def mpow(x,n):
    num=1
    while n > 0:
        if n&1:
            num=num*x%mod
        x=x*x%mod
        n=n>>1
    return(num)

for i in range(0,ferumaC-1):
    fac[i+1]=(fac[i]*(i+1))%mod
    ifac[i+1]=ifac[i]*mpow(i+1,mod-2)%mod
def comb(a,b):
    if a==0 and b==0:return(1)
    if a<b or a<0:return(0)
    tmp=ifac[a-b]*ifac[b]%mod
    return(tmp*fac[a]%mod)


from fractions import gcd
def lcm(a,b):
    return(a*b//gcd(a,b))

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

value=A[0]
for i in range(1,N):
    value=lcm(value,A[i])
value%=mod
count=0
for a in A:
    count+=value*(mpow(a,mod-2))%mod
    count%=mod
print(count)
### BUGGY CODE ###

from functools import reduce

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


res = [0] * (n-k+1)
res[0] = reduce(lambda x, y: x*y , A[0:k+1])

for i in range(1, n-k+1):
    res[i] = res[i-1]//A[i-1]*A[i+k-1]
    print('Yes' if res[i-1] < res[i] else 'No')




### FIXED CODE ###

from functools import reduce

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

for i in range(0, n-k):
    print('Yes' if A[i] < A[i+k] else 'No')
### BUGGY CODE ###

n, d, a = map(int, input().split())
xh = []
for _ in range(n):
    x, h = map(int, input().split())
    xh.append([x, h])

xh.sort(key=lambda x:x[0])
ind = 0
ans = 0
while ind<n:
    end = xh[ind][0]+2*d
    cnt = (xh[ind][1]+a-1)//a
    ans += cnt
    ind += 1
    i = ind
    while i<n and xh[i][0]<=end:
        xh[i][1] -= a*cnt
        i += 1
    while ind<n and xh[ind][1]<=0:
        ind += 1
print(ans)

### FIXED CODE ###

n, d, a = map(int, input().split())
xh = []
for _ in range(n):
    x, h = map(int, input().split())
    h = (h+a-1)//a
    xh.append([x, h])

xh.sort(key=lambda x:x[0])

def bisect(x):
    i_min=0
    i_max=n
    while i_min<i_max:
        i = (i_min+i_max)//2
        if xh[i][0]<=x:
            i_min = i+1
        else:
            i_max = i
    return i_min

ans = 0
accu = 0
out = [0]*(n+1)
for i, (x, h) in enumerate(xh):
    accu -= out[i]
    hp = h-accu
    if hp<=0:
        continue
    accu += hp
    ans += hp
    out[bisect(x+2*d)] += hp 
print(ans)
### BUGGY CODE ###

a, b, x = map(int, input().split())
ans = 0
for i in range (a,b+1):
    if i%x == 0:
        ans += 1
    else:
        continue
print(ans)

### FIXED CODE ###

a, b, x = map(int, input().split())
A = b//x
B = a//x
if a%x == 0:
    print(A-B+1)
else:
    print(A-B)
### BUGGY CODE ###

from collections import deque
n,m = map(int,input().split())

a = []
for _ in range(m):
    a.append(list(map(int,input().split())))

b = [[] for i in range(n)]
for i in range(m):
    b[a[i][1]-1].append(a[i][0])
    b[a[i][0]-1].append(a[i][1])
    
c = [-1 for i in range(n)]
c[0] = 0
q = deque([1])
now = 0
count = 0
while q:
    #print(c,q, now)
    count = count + 1
    if count > 2 * m:
        print("No")
        exit()
    now = q.popleft() - 1
    for i in range(len(b[now])):
        if c[b[now][i] - 1] == -1 and b[now][i] not in q:
            q.append(b[now][i])
            c[q[-1] - 1] = now + 1
            #print(c)
            
#print(c)
print("Yes")
for i in range(1,len(c)):
    print(c[i])

### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())

b = [[] for i in range(n)]
for i in range(m):
    a=list(map(int,input().split()))
    b[a[1]-1].append(a[0])
    b[a[0]-1].append(a[1])
    
c = [-1 for i in range(n)]
c[0] = 0
q = deque([1])
now = 0
count = 0
while q:
    #print(c,q, now)
    count = count + 1
    if count > n:
        print("No")
        exit()
    now = q.popleft() - 1
    for i in range(len(b[now])):
        #count = count + 1
        #print(now+1, "=>", b[now][i])
        if c[b[now][i] - 1] == -1:
            q.append(b[now][i])
            c[q[-1] - 1] = now + 1
            #print(c)
            
#print(count)
print("Yes")
for i in range(1,len(c)):
    print(c[i])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
MAX = 60

acc = [0] * MAX
ans = [0] * MAX

num = a[0]
for i in range(MAX):
    if num & 1:
        acc[i] = 1
    num >>= 1

for i, e in enumerate(a[1:], 1):
    for j in range(MAX):
        if e & 1:
            ans[j] += i - acc[j]
            acc[j] += 1
        else:
            ans[j] += acc[j]

        e >>= 1

ans_num = 0
for i, e in enumerate(ans):
    ans_num += pow(2, i, mod) * e
    ans_num %= mod

print(ans_num)


### FIXED CODE ###

import numpy as np

MOD = 10 ** 9 + 7

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

ans = 0
for n in range(62):
    B = (A >> n) & 1
    x = np.count_nonzero(B)
    y = N - x
    mul = x * y
    for _ in range(n):
        mul *= 2
        mul %= MOD
    ans += mul

ans %= MOD
print(ans)
### BUGGY CODE ###

from collections import defaultdict

mem = {}


def binomialCoef(n, k):
    if n < k:
        return 0
    if n in mem.keys():
        return mem[n]
    C = [[0 for x in range(k + 1)] for x in range(n + 1)]

    # Calculate value of Binomial Coefficient in bottom up manner
    for i in range(n + 1):
        for j in range(min(i, k) + 1):
            # Base Cases
            if j == 0 or j == i:
                C[i][j] = 1

            # Calculate value using previously stored values
            else:
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j]

    mem[n] = C[n][k]
    return mem[n]


if __name__ == '__main__':
    n = int(input())
    xs = [int(s) for s in input().split()]
    freq = defaultdict(int)
    xs_res = defaultdict(int)

    for n in xs:
        freq[n] += 1
        if freq[n] > 2:
            xs_res[n] *= 2
        if freq[n] > 1:
            xs_res[n] += 1

    res = 0

    for k in range(len(xs)):
        res = 0
        for num in freq.keys():
            res += binomialCoef(freq[num] if num != xs[k] else freq[num] - 1, 2)
        print(res)


### FIXED CODE ###

from collections import defaultdict


def num_combinations(_n):
    return _n * (_n - 1) // 2


if __name__ == '__main__':
    n = int(input())
    xs = [int(s) for s in input().split()]
    freq = defaultdict(int)

    for n in xs:
        freq[n] += 1

    total = sum([num_combinations(n) for n in freq.values()])
    for x in xs:
        print(total - (freq[x] - 1))
### BUGGY CODE ###

N = int(input())
table = [[int(i) for i in input().split()] for N in range(N)]

n = 0
for i in range(N):
    for j in range(i):
        if n < abs(table[i][0]-table[j][0]) + abs(table[i][1]-table[j][1]):
            n = abs(table[i][0]-table[j][0]) + abs(table[i][1]-table[j][1])

print(n)


### FIXED CODE ###

N = int(input())
table = [[int(i) for i in input().split()] for N in range(N)]

a = -1
b = 10**10
c = -10**10
d = 10**10
for i in range(N):
    p = table[i][0]
    q = table[i][1]
    if a < p+q:
        a = p+q
    if b > p+q:
        b = p+q
    if c < p-q:
        c = p-q
    if d > p-q:
        d = p-q

print(max(a-b,c-d))
### BUGGY CODE ###

import sys
a = input()
S = [s for s in a]
# #print(l)

cnt = 0
while True:
    b = a
    a = a.replace("BW","WB",1)
    if b != a:
        cnt += 1
    else:
        print(cnt)
        sys.exit(0)

### FIXED CODE ###

import sys
a = [ c for c in input()]
B = 0
W = 0
for i in range(len(a)):
    if a[i] == "B":
        B += 1
    else:
        W += B

print(W)
### BUGGY CODE ###

S = input()
Q = int(input())

for _ in range(Q):
    IN = list(map(str,input().split()))
    if IN[0] == "1":
        S = S[::-1]
        continue
    _,F,C = IN
    if F == "1":
        S = C + S
    else:
        S += C

print(S)

### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())

flag = False
for _ in range(Q):
    IN = list(map(str,input().split()))

    if IN[0] == "1":
        flag = not flag
        continue

    _,F,C = IN
    if flag:
        if F == "1":
            S.append(C)
        else:
            S.appendleft(C)
    else:
        if F == "1":
            S.appendleft(C)
        else:
            S.append(C)

if flag:
    print(*reversed(S),sep="")
else:
    print(*S,sep="")
### BUGGY CODE ###

n = int(input())
l = [] 
for i in range(n):
	list = [" "] * n
	a = int(input())
	for j in range(a):
		data = input().split(" ")
		x = int(data[0])
		y = data[1]
		list[x-1] = y
	l.append(list)
m = 0
for i in range(2**n):
	s = bin(i)
	s = s[2:]
	s = s.zfill(n)
	ll = []
	th = [" "] * n
	for j in range(n):
		if int(s[j]) == 1:
			ll.append(l[j])
			th[j] = "1"
		elif int(s[j]) == 0:
			th[j] = "0" 
	te = 0
	for j in range(n):
		cu = "2"
		for k in range(len(ll)):
			if ll[k][j] == "1" and th[j] != "1":
				te = 1
			elif ll[k][j] == "0" and th[j] != "0":
				te = 1
			if ll[k][j] == "1" and cu == "2":
				cu = "1"
			elif ll[k][j] == "0" and cu == "2":
				cu = "0"
			elif ll[k][j] == "0" and cu == "1":
				te = 1
			elif ll[k][j] == "1" and cu == "0":
				te = 1
	if te == 0:
		f = len(ll)
		if f > m:
			m = f
print(m)

### FIXED CODE ###

n = int(input())
l = [] 
for i in range(n):
	list = [" "] * n
	a = int(input())
	for j in range(a):
		data = input().split(" ")
		x = int(data[0])
		y = data[1]
		list[x-1] = y
	l.append(list)
m = 0
for i in range(2**n):
	s = bin(i)
	s = s[2:]
	s = s.zfill(n)
	ll = []
	th = [" "] * n
	for j in range(n):
		if int(s[j]) == 1:
			ll.append(l[j])
			th[j] = "1"
		elif int(s[j]) == 0:
			th[j] = "0" 
	te = 0
	for j in range(n):
		for k in range(len(ll)):
			if ll[k][j] == "1" or ll[k][j] == "0":
				if ll[k][j] != th[j]:
					te = 1
	if te == 0:
		f = len(ll)
		if f > m:
			m = f
print(m)
### BUGGY CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
ma = 80*2*80
DP = [[[0]*ma for i in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        k = abs(a[i][j]-b[i][j])
        up = (i+j+1)*80+1
        if i==0 and j==0:
            DP[i][j][k] = 1
            continue
        elif i == 0:
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k]
        elif j == 0:
            for l in range(up):
                DP[i][j][l] = DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
        else:
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k] | DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
print(DP[-1][-1].index(1))

### FIXED CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
ma = 80*2*80
DP = [[[0]*ma for i in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        k = abs(a[i][j]-b[i][j])
        if i==0 and j==0:
            DP[i][j][k] = 1
            continue
        elif i == 0:
            up = min((i+j+1)*80+1, ma-k)
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k]
        elif j == 0:
            for l in range(up):
                DP[i][j][l] = DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
        else:
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k] | DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
for i in range(ma):
    if DP[-1][-1][i]:
        print(i)
        exit()
### BUGGY CODE ###

from fractions import gcd

n = int(input())
ans = 0

for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            temp = gcd(i,j)
            ans += gcd(temp, k)
            
print(ans)

### FIXED CODE ###

from fractions import gcd
from collections import defaultdict

n = int(input())
temp = defaultdict(int)
ans = 0

for i in range(1, n+1):
    for j in range(1, n+1):
      x = gcd(i,j)
      temp[x] += 1

for k,v in temp.items():
  for w in range(1, n+1):
    ans += gcd(k,w)* v

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

from collections import deque

N, M = map(int, input().split())
Edge = [[] for _ in range(N)]
Start = {a for a in range(N)}
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    Edge[x].append(y)
    if y in Start:
        Start.remove(y)

Q = deque(Start)

DP = [0] * N

while Q:
    now = Q.popleft()
    for nex in Edge[now]:
        if DP[nex] < DP[now] + 1:
            DP[nex] = DP[now] + 1
            Q.append(nex)
print(max(DP))



### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

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


def long(x):
    if len(Edge[x]) == 0:
        Far[x] = 0
        return 0
    if Far[x] >= 0:
        return Far[x]
    r = 0
    for i in Edge[x]:
        l = long(i) + 1
        r = max(r, l)
    Far[x] = r
    return r


for i in range(N):
    long(i)
print(max(Far))
### BUGGY CODE ###

N=int(input())
S=list(input())
ans=N
for i in range(N):ans=min(ans,S[:i].count('W')+S[i:].count('E'))
print(ans)

### FIXED CODE ###

N=int(input())
S=list(input())
e,w=[0]*(N+1),[0]*(N+1)
for i in range(1,N+1):
    w[i] += w[i-1] + (1 if S[i-1]=='W' else 0)
    e[i] += e[i-1] + (1 if S[i-1]=='E' else 0)
ans=N
for i in range(N):
    ans=min(ans,w[i]+e[-1]-e[i+1])
print(ans)
### BUGGY CODE ###

N,M = map(int, input().split())
A = [int(input()) for i in range(M)]
dp = [0]*(N+1)
dp[0]=1
if 1 in A:
    dp[1]= 0
else:
    dp[1]=1
for i in range(2,N+1):
    if i in A:
        dp[i] == 0
    else:
        dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

### FIXED CODE ###

N,M = map(int, input().split())
A = [int(input()) for i in range(M)]
dp = [0]*(N+1)
for k in A:
    dp[k]="E"
dp[0]=1
if dp[1]=="E":
    dp[1]= 0
else:
    dp[1]= 1
for i in range(2,N+1):
    if dp[i]=="E":
        dp[i] = 0
    else:
        dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])
### BUGGY CODE ###

from itertools import permutations

N, M, R = map(int, input().split())

visit = list(map(int, input().split()))
g = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c

for i in range(N):
    for j in range(N):
        for k in range(N):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

cost = float('inf')
visit = permutations(visit)
for town in visit:
    c = 0
    for i in range(len(town) - 1):
        c += g[town[i] - 1][town[i + 1] - 1]
    cost = min(cost, c)
print(cost)


### FIXED CODE ###

from itertools import permutations

N, M, R = map(int, input().split())

visit = list(map(int, input().split()))
g = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    g[i][i] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c


def dijkstra(start):
    c_l = [float('inf')] * N
    c_l[start] = 0
    visited = [False] * N
    while True:
        min_v = float('inf')
        next = -1
        visited[start] = True
        for i in range(N):
            if visited[i]:
                continue
            if g[start][i]:
                d = c_l[start] + g[start][i]
                if d < c_l[i]:
                    c_l[i] = d
                if min_v > c_l[i]:
                    min_v = c_l[i]
                    next = i
        start = next
        if next == -1:
            break
    return c_l


cost_list = []
for i in range(N):
    cost_list.append(dijkstra(i))

cost = float('inf')
for town in permutations(visit):
    c = 0
    for i in range(R - 1):
        c += cost_list[town[i] - 1][town[i + 1] - 1]
    cost = min(cost, c)
print(cost)
### BUGGY CODE ###

# ABC 061: C – Big Array
N, K = [int(i) for i in input().split()]
a, b = [], []
for _ in range(N):
    tmp = input().split()
    a.append(int(tmp[0]))
    b.append(int(tmp[1]))

sequence = []

for i in range(N):
    sequence += [a[i]] * b[i]

sequence.sort()
print(sequence[K - 1])

### FIXED CODE ###

# ABC 061: C – Big Array
N, K = [int(i) for i in input().split()]
a, b = [], []
for _ in range(N):
    tmp = input().split()
    a.append(int(tmp[0]))
    b.append(int(tmp[1]))

cnt = [0] * (100000 + 1)

for i in range(N):
    cnt[a[i]] += b[i]

for j in range(100000 + 1):
    if K <= cnt[j]:
        print(j)
        break
    K -= cnt[j]
### BUGGY CODE ###

cubes = input()

removed_cubes_count = 0

while True:
    removed_cubes = cubes.replace('01', '')
    removed_cubes = removed_cubes.replace('10', '')

    removed_cubes_count += len(cubes) - len(removed_cubes)

    if len(cubes) == len(removed_cubes):
        break

    cubes = removed_cubes

print(removed_cubes_count)


### FIXED CODE ###

cube = input()

zero_count = 0
one_count = 0

for i in range(len(cube)):
    if cube[i] == '0':
        zero_count += 1
    else:
        one_count += 1

if zero_count < one_count:
    print(zero_count * 2)
else:
    print(one_count * 2)
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline

n = int(input())
a = int(input())

color = [a]
color_min = a

for _ in range(1, n):
    a = int(input())
    if color_min >= a:
        j = bisect.bisect_left(color, a)
        color = color[:j] + [a] + color[j:]
        color_min = a
    else:
        j = bisect.bisect_left(color, a)
        color = color[:j-1] + color[j:]
        j = bisect.bisect_left(color, a)
        color = color[:j] + [a] + color[j:]
        color_min = color[0]

print(len(color))


### FIXED CODE ###

from collections import deque
from bisect import bisect_left

n = int(input())
a = [int(input()) for _ in range(n)]

b = deque([])

for ai in a:
    if len(b) == 0:
        b.append(ai)
    else:
        if ai <= b[0]:
            b.appendleft(ai)
        else:
            idx = bisect_left(b, ai)
            b[idx-1] = ai

print(len(b))