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

import numpy as np
hp, n = map(int,input().split())

list = np.zeros((n,2),dtype=int)
for i in range(n):
    list[i][0], list[i][1] = map(int,input().split())

dp = np.full((n+1, hp+1), 100000000000000000,dtype=int)

dp[0][0] = 0
for i, lista in enumerate(dp):
    dp[i][0] = 0
    for j, value in enumerate(lista):
        if i == 0:
            continue
        if j < list[i-1][0]:
            dp[i][j] = min(list[i-1][1], dp[i-1][j])
        else:
            target = j - list[i-1][0]
            dp[i][j] = min((dp[i][target] + list[i-1][1]), dp[i-1][j])

print(int(dp[n][hp]))




### FIXED CODE ###


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

list = [[0] * 2 for i in range(n)]
for i in range(n):
    list[i][0], list[i][1] = map(int,input().split())

dp = [[10000000000] * (hp+1) for i in range(n+1)]

dp[0][0] = 0
for i, lista in enumerate(dp):
    dp[i][0] = 0
    for j, value in enumerate(lista):
        if i == 0:
            continue
        if j < list[i-1][0]:
            dp[i][j] = min(list[i-1][1], dp[i-1][j])
        else:
            target = j - list[i-1][0]
            dp[i][j] = min((dp[i][target] + list[i-1][1]), dp[i-1][j])

print(int(dp[n][hp]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

FACT=[1]
for i in range(1,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

DP=[0]*(N+1)
DP[0]=1

for k in range(K):
    use=A[k]

    NDP=[0]*(N+1)

    for i in range(N+1):
        ANS=0
        for j in range(N+1):
            ANS=(ANS+DP[j]*Combi(N-j,i-j)*Combi(N-(i-j),use-(i-j)))%mod

        NDP[i]=ANS

    DP=NDP

print(DP[N])

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

Combi=[[] for i in range(N+1)]
Combi[0]=[1,0]

for i in range(1,N+1):
    Combi[i].append(1)
    for j in range(i):
        Combi[i].append((Combi[i-1][j]+Combi[i-1][j+1])%mod)
    Combi[i].append(0)

DP=[0]*(N+1)
DP[0]=1

for k in range(K):
    use=A[k]

    NDP=[0]*(N+1)

    for i in range(N+1):
        ANS=0
        for j in range(i+1):
            if use-(i-j)>=0:
                ANS=(ANS+DP[j]*Combi[N-j][i-j]*Combi[N-(i-j)][use-(i-j)])%mod

        NDP[i]=ANS

    #print(DP)

    DP=NDP

print(DP[N])
### BUGGY CODE ###

import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
a = list(map(float, input().split()))
one = a.count(1)
two = a.count(2)
three = a.count(3)

#dp[i][j][k]は残1がi枚、残2がj枚、残3がk枚のときの残り回数の期待値
dp = [[[-1 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 0
#メモ化再帰
def rec(i, j, k):
    if dp[i][j][k] > -1:
        return dp[i][j][k]

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

print(rec(one, two, three))

### FIXED CODE ###

import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
a = list(map(float, input().split()))
one = a.count(1)
two = a.count(2)
three = a.count(3)

#dp[i][j][k]は残1がi枚、残2がj枚、残3がk枚のときの残り回数の期待値
dp = [[[0.0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 0.0

def rec(i, j, k):
    if dp[i][j][k] > -1:
        return dp[i][j][k]

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

for k in range(three + 1):
    for j in range(two + three + 1 - k):
        for i in range(one + two + three + 1 - k - j):
            if i + j + k == 0:
                continue

            res = 0
            if i > 0:
                res += dp[i - 1][j][k] * i / (i + j + k)
            if j > 0:
                res += dp[i + 1][j - 1][k] * j / (i + j + k)
            if k > 0:
                res += dp[i][j + 1][k - 1] * k / (i + j + k)
            res += N / (i + j + k)
            dp[i][j][k] = res

print(dp[one][two][three])
### BUGGY CODE ###

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    for i in range(k):
        memo = [0] * (n + 1)
        for j, aa in enumerate(a):
            memo[max(0, j - aa)] += 1
            memo[min(n, j + aa + 1)] -= 1
        for j in range(n):
            memo[j + 1] += memo[j]
        a = memo[:-1]
        if set(a) == n:
            break
    print(*a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    for i in range(k):
        memo = [0] * (n + 1)
        for j, aa in enumerate(a):
            memo[max(0, j - aa)] += 1
            memo[min(n, j + aa + 1)] -= 1
        for j in range(n):
            memo[j + 1] += memo[j]
        a = memo[:-1]
        if a == [n] * n:
            break
    print(*a)


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

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

numbers = []

num = A[1]
for i in range(2, N):
    num = num ^ A[i]
numbers.append(num)

for i in range(1, N):
    num = A[0]
    for j in range(1,N):
        if j == i:
            continue
        else:
            num = num ^ A[j]
    numbers.append(num)

print(*numbers)


### FIXED CODE ###

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

numbers = []

s = A[0]
for i in range(1, N):
    s = s ^ A[i]
for i in range(N):
    numbers.append(s ^ A[i])

print(*numbers)
### BUGGY CODE ###

from heapq import heappush,heappop
n=int(input())
xy=[]
yx=[]
for i in range(n):
    x,y=map(int,input().split())
    xy.append([x,y,i])
    yx.append([y,x,i])
xy.sort()
yx.sort()
data=[[0,0] for i in range(n)]
for i in range(n):
    x,y,a=xy[i]
    data[a][0]=i
    y,x,a=yx[i]
    data[a][1]=i
ans=0
que=[[0,0]]
flag=[0]*n
count=0
while count<=n:
    l,a=heappop(que)
    if flag[a]==1:
        continue
    ans+=l
    flag[a]=1
    count+=1
    if count==n:
        break
    b,c=data[a]
    xb=xy[b][0]
    yc=yx[c][0]
    if 1<=b<=n-2:
        xd,yd,d=xy[b-1]
        xe,ye,e=xy[b+1]
        if flag[d]==0:
            heappush(que,[abs(xd-xb),d])
        if flag[e]==0:
            heappush(que,[abs(xe-xb),e])
    elif b==0:
        xe,ye,e=xy[1]
        if flag[e]==0:
            heappush(que,[abs(xb-xe),e])
    else:
        xd,yd,d=xy[n-2]
        if flag[d]==0:
            heappush(que,[abs(xb-xd),d])
    if 1<=c<=n-2:
        yg,xg,g=yx[c+1]
        yf,xf,f=yx[c-1]
        if flag[f]==0:
            heappush(que,[abs(yf-yc),f])
        if flag[g]==0:
            heappush(que,[abs(yg-yc),g])
    elif c==0:
        yg,xg,g=yx[1]
        if flag[g]==0:
            heappush(que,[abs(yg-yc),g])
    else:
        yf,xf,f=yx[n-2]
        if flag[f]==0:
            heappush(que,[abs(yf-yc),f])
print(ans)

### FIXED CODE ###

from heapq import heappush,heappop
n=int(input())
xy=[]
yx=[]
for i in range(n):
    x,y=map(int,input().split())
    xy.append([x,y,i])
    yx.append([y,x,i])
xy.sort()
yx.sort()
data=[[0,0] for i in range(n)]
for i in range(n):
    x,y,a=xy[i]
    data[a][0]=i
    y,x,a=yx[i]
    data[a][1]=i
ans=0
que=[[0,0]]
flag=[0]*n
count=0
while count<=n:
    l,a=heappop(que)
    if flag[a]==1:
        continue
    ans+=l
    flag[a]=1
    count+=1
    if count==n:
        break
    b,c=data[a]
    xb=xy[b][0]
    yc=yx[c][0]
    if 1<=b<=n-2:
        xd,yd,d=xy[b-1]
        xe,ye,e=xy[b+1]
        if flag[d]==0:
            heappush(que,[abs(xd-xb),d])
        if flag[e]==0:
            heappush(que,[abs(xe-xb),e])
    elif b==0:
        xe,ye,e=xy[1]
        if flag[e]==0:
            heappush(que,[abs(xb-xe),e])
    else:
        xd,yd,d=xy[n-2]
        if flag[d]==0:
            heappush(que,[abs(xb-xd),d])
    if 1<=c<=n-2:
        yg,xg,g=yx[c+1]
        yf,xf,f=yx[c-1]
        if flag[f]==0:
            heappush(que,[abs(yf-yc),f])
        if flag[g]==0:
            heappush(que,[abs(yg-yc),g])
    elif c==0:
        yg,xg,g=yx[1]
        if flag[g]==0:
            heappush(que,[abs(yg-yc),g])
    else:
        yf,xf,f=yx[n-2]
        if flag[f]==0:
            heappush(que,[abs(yf-yc),f])
print(ans)
### BUGGY CODE ###

def resolve():
    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(k):
        nxt = [1]*n
        for j in range(len(a)):
            if a[j] == 0:
                continue
            r = min(j + a[j], n-1) #look right
            l = max(j-a[j], 0) #look left
            for m in range(j+1, r+1):
                nxt[m] = min(nxt[m]+1,n)

            for m in range(l, j):
                nxt[m] = min(nxt[m]+1,n)


        a, nxt = nxt, a
        if a == nxt:
            break
    print(*a)

resolve()

### FIXED CODE ###

def resolve():
    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(k):
        nxt = [0]*n
        for j in range(len(a)):
            r = min(j + a[j], n-1) #look right
            l = max(j-a[j], 0) #look left
            nxt[l] += 1
            if r+1 < n:
                nxt[r+1] -= 1
        b = [0] *n
        for j in range(len(a)):
            if j== 0:
                b[j] = nxt[j]
            else:
                b[j] = (nxt[j]+b[j-1])
        a, b = b, a
        if a == b:
            break
    print(*a)
resolve()
### BUGGY CODE ###

N = int(input())
X = int(input(),2)
from collections import Counter


def pop_count(n):
    return n%Counter(bin(n))['1']
n = 7
ans = 0
for i in range(N-1,-1,-1):
    n = X^pow(2,i)
    while n != 0:
        n = pop_count(n)
        ans += 1
    print(ans)
    ans = 0

### FIXED CODE ###

N = int(input())
X = input()
bin_X = int(X, 2)
cnt = 0
for i in X:
    if i == '1':
        cnt += 1


def bit_count(bits):
    cnt = 0
    while bits:
        bits = bits & (bits - 1)
        bits >> 1
        cnt += 1
    return cnt


def pop_counter(n):
    return n % bit_count(n)


ans = 0
xp = bin_X % (cnt + 1)
if cnt != 1:
    xm = bin_X % (cnt - 1)
else:
    xm = 0
for n, i in enumerate(X):
    if i == '0':
        tmp = xp + pow(2, N - n - 1, cnt + 1)
        tmp %= cnt + 1
    elif cnt != 1:
        tmp = xm - pow(2,N-n-1,cnt-1)
        tmp %= cnt -1
    else:
        print(0)
        continue
    ans = 1
    while tmp != 0:
        tmp = pop_counter(tmp)
        ans += 1
    print(ans)
### BUGGY CODE ###

import math

from functools import lru_cache
#上手くいかない時は下
# from functools32 import lru_cache 

@lru_cache(None)
def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def search_divisor_num_1(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num
    
N=int(input())
cnt=0
for i in range(1,N):
    cnt += search_divisor_num_1(N-i)
    
print(cnt)

### FIXED CODE ###

N=int(input())

ans=0
for a in range(1,N):
    ans += (N-1)//a
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
L = [[0]*W for i in range(H)]
R = [[0]*W for i in range(H)]
U = [[0]*W for i in range(H)]
D = [[0]*W for i in range(H)]
LAMP = [[0]*W for i in range(H)]
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      L[i][j] = 0
    elif j == 0:
      L[i][j] = 1
    else:
      L[i][j] = L[i][j-1] + 1
    if S[i][j] == "#":
      U[i][j] = 0
    elif i == 0:
      U[i][j] = 1
    else:
      U[i][j] = U[i-1][j] + 1
      
for i in range(H-1,-1,-1):
  for j in range(W-1,-1,-1):
    if S[i][j] == "#":
      R[i][j] = 0
    elif j == W-1:
      R[i][j] = 1
    else:
      R[i][j] = R[i][j+1] + 1
    if S[i][j] == "#":
      D[i][j] = 0
    elif i == H-1:
      D[i][j] = 1
    else:
      D[i][j] = D[i+1][j] + 1
    if S[i][j] != "#":
       ans = max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
L = [[0]*W for i in range(H)]
R = [[0]*W for i in range(H)]
U = [[0]*W for i in range(H)]
D = [[0]*W for i in range(H)]
LAMP = [[0]*W for i in range(H)]
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      L[i][j] = 0
    elif j == 0:
      L[i][j] = 1
    else:
      L[i][j] = L[i][j-1] + 1
    if S[i][j] == "#":
      U[i][j] = 0
    elif i == 0:
      U[i][j] = 1
    else:
      U[i][j] = U[i-1][j] + 1
      
for i in range(H-1,-1,-1):
  for j in range(W-1,-1,-1):
    if S[i][j] == "#":
      R[i][j] = 0
    elif j == W-1:
      R[i][j] = 1
    else:
      R[i][j] = R[i][j+1] + 1
    if S[i][j] == "#":
      D[i][j] = 0
    elif i == H-1:
      D[i][j] = 1
    else:
      D[i][j] = D[i+1][j] + 1
    if S[i][j] != "#":
       ans = max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

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

n = int(input())
a = sorted([x, i] for i, x in enumerate(list(map(int, input().split()))))
f = [[0 for j in range(n)] for i in range(n)]
for i in range(n-1, -1, -1):
    f[i][i] = a[0][0]*abs(a[0][1]-i)
    for j in range(i+1, n):
        f[i][j] = max(f[i+1][j]+a[j-i][0]*abs(a[j-i][1]-i), f[i][j-1]+a[j-i][0]*abs(a[j-i][1]-j))
print(f[0][n-1])

### FIXED CODE ###

n = int(input())
a = sorted([x, i] for i, x in enumerate(list(map(int, input().split()))))
f = [[0 for j in range(n)] for i in range(n)]
for i in range(n-1, -1, -1):
    f[i][i] = a[0][0]*abs(a[0][1]-i)
    for j in range(i+1, n):
        f[i][j] = max(f[i+1][j]+a[j-i][0]*abs(a[j-i][1]-i), f[i][j-1]+a[j-i][0]*abs(a[j-i][1]-j))
print(f[0][n-1])
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
S = []
for i in range(H):
    S.append(input())


def exists(h, w):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    elif S[h][w] == "#":
        return False
    else:
        return True


costs = [[-1] * W for _ in range(H)]
passed = [[0] * W for _ in range(H)]
costs[C_h - 1][C_w - 1] = 0
d = deque()
d.append((C_h - 1, C_w - 1))
while d:
    h, w = d.popleft()
    c = costs[h][w]
    if passed[h][w] == 1:
        continue
    for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        hh = h + i
        ww = w + j
        if exists(hh, ww):
            if (hh, ww) in d:
                d.remove((hh, ww))
            costs[hh][ww] = c
            d.appendleft((hh, ww))
    for i in range(5):
        for j in range(5):
            hh = h + i - 2
            ww = w + j - 2
            if exists(hh, ww):
                if costs[hh][ww] == -1:
                    costs[hh][ww] = c + 1
                    d.append((hh, ww))
    passed[h][w] = 1
print(costs[D_h - 1][D_w - 1])


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
W_ = W + 4
H_ = H + 4
S = ["#" * W_] * 2 + ["##" + input() + "##" for _ in range(H)] + ["#" * W_] * 2

INF = float('inf')
costs = [[INF] * W_ for _ in range(H_)]
costs[C_h + 1][C_w + 1] = 0
d0 = deque()
d0.append((C_h + 1, C_w + 1, 0))
d1 = deque()
while d0:
    h, w, c = d0.popleft()
    d1.append((h, w, c))
    for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        hh = h + i
        ww = w + j
        if S[hh][ww] == '.' and c < costs[hh][ww]:
            costs[hh][ww] = c
            d0.appendleft((hh, ww, c))
    if len(d0) == 0:
        while d1:
            h, w, c = d1.popleft()
            for i in range(5):
                for j in range(5):
                    hh = h + i - 2
                    ww = w + j - 2
                    if S[hh][ww] == '.' and c + 1 < costs[hh][ww]:
                        costs[hh][ww] = c + 1
                        d0.append((hh, ww, c + 1))

if costs[D_h + 1][D_w + 1] != INF:
    ans = costs[D_h + 1][D_w + 1]
else:
    ans = -1
print(ans)
### BUGGY CODE ###

print(sum(range(int(input()))))

### FIXED CODE ###

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

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

for k in range(0, K):
    work = [0] * N
    for i in range(0, N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])
        work[l] += 1
        if (r + 1 < N):
            work[r + 1] -= 1
    for i in range(1, N):
        work[i] += work[i - 1]
    A = work
    if (all([item == N for item in A])):
        break

print(" ".join([str(item) for item in work]))

### FIXED CODE ###

import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))
### BUGGY CODE ###

import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def S(): return input().rstrip()
def LIR(n): return [S().split() for i in range(n)]

def main():
    s = S()
    Q = I()
    Qu = LIR(Q)
    for que in Qu:
        if que[0] == '1':
            s = s[::-1]
        else:
            if que[1] == '1':
                s = ''.join([que[2], s])
            else:
                s = ''.join([s, que[2]])
    print(s)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict, deque
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def S(): return input().rstrip()
def LIR(n): return [S().split() for i in range(n)]

def main():
    s = S(); Q = I()
    mode = 2
    d = deque(s)

    for i in range(Q):
        query = S()
        if query[0] == "1": mode = 3 - mode
        else:
            t, f, c = map(str, query.split())
            if (int(f) + mode)% 2  == 0: d.append(c)
            else: d.appendleft(c)
    if mode == 2: print(''.join(d))
    else: print(''.join(list(d)[::-1]))

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

def permutation(lst):
    if len(lst) == 0:
        return []
    if len(lst) == 1:
        return[lst]
    l = []
    for i in range(len(lst)):
        m = lst[i]
        remLst = lst[:i] + lst[i+1:]
        for p in permutation(remLst):
            l.append([m] + p)
    return l

N,M,R = map(int,input().split())
rseq = list(map(int,input().split()))
graph = [[] for x in range(N+1)]

for i in range(M):
    A,B,C = map(int,input().split())
    graph[A].append((B,C))
    graph[B].append((A,C))

dist = [[(2 * (10 ** 8)) for x in range(N+1)] for x in range(N+1)]
#FloydWarshall
for i in range(N+1):
    dist[i][i] = 0
for i in range(1,N+1):
    for j in range(len(graph[i])):
        dist[i][graph[i][j][0]] = graph[i][j][1]
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
rpsec = permutation(rseq)
minimum = 200000000
for p in rpsec:
    total = 0
    for j in range(1,R):
        total += dist[p[j]][p[j-1]]
    if total < minimum:
        minimum = total
print(minimum)

### FIXED CODE ###

from itertools import permutations
 
 
def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
                new_dist = dp[i][k] + dp[k][j]
                if dp[i][j] > new_dist:
                    dp[i][j] = new_dist
 
 
def main():
    N, M, R = [int(x) for x in input().split()]
    destinations = [int(x) for x in input().split()]
    dp = [[float('inf')]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0
    for _ in range(M):
        f, t, d = [int(x) for x in input().split()]
        dp[f][t] = dp[t][f] = d
 
    warshallFloyd(N+1, dp)
 
    minimum_cost = float('inf')
    for route in permutations(destinations, len(destinations)):
        cost = 0
        while len(route) > 1:
            f, t = route[0], route[1]
            cost += dp[f][t]
            if cost > minimum_cost:
                break
            route = route[1:]
        if cost < minimum_cost:
            minimum_cost = cost
    print(minimum_cost)
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))

for t in T:
    if t in D:
        D.remove(t)
    else:
        print("NO")
        break
else:
    print("YES")

### FIXED CODE ###

N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))

dicD = {}
dicT = {}

for d in D:
    if d not in dicD:
        dicD[d] = 0
    dicD[d] += 1

for t in T:
    if t not in dicT:
        dicT[t] = 0
    dicT[t] += 1

for t in dicT:
    if t not in dicD:
        print("NO")
        break
    elif dicT[t] > dicD[t]:
        print("NO")
        break
else:
    print("YES")
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    SP = [input().split() for i in range(M)]
    wa_num = 0
    wa_num_temp = {}
    ac_num = 0
    ansed = []
    for sp in SP:
        if sp[0] not in wa_num_temp:
            wa_num_temp[sp[0]] = 0
        if sp[1] == "WA" and sp[0] not in ansed:
            wa_num_temp[sp[0]] += 1
        elif sp[1] == "AC" and sp[0] not in ansed:
            ac_num += 1
            wa_num += wa_num_temp[sp[0]]
            ansed.append(sp[0])

    print(ac_num, wa_num)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    from sys import stdin
    input = stdin.readline
    N, M = map(int, input().split())
    SP = [list(input().split()) for i in range(M)]
    was = [0] * N
    acs = [0] * N
    penaltyCount = 0
    for sp in SP:
        if acs[int(sp[0])-1] == 1:
            continue
        if acs[int(sp[0])-1] == 0 and sp[1] == "WA":
            was[int(sp[0])-1] += 1
        elif acs[int(sp[0])-1] == 0 and sp[1] == "AC":
            acs[int(sp[0])-1] = 1
            penaltyCount += was[int(sp[0])-1]

    print(sum(acs), penaltyCount)


if __name__ == "__main__":
    main()