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

import sys

H, W = map(int, sys.stdin.readline().strip().split())
grid = []
for _ in range(H):
    grid.append(list(sys.stdin.readline().strip()))

# (x, y)B$Nx, yBJ}8~$Nscore [a, b]
scores = [[[0, 0] for _ in range(W)] for _ in range(H)]
for y in range(H):
    start = 0
    count = 0
    for x in range(W):
        if grid[y][x] == "#" or x == W-1:
            if x == W-1 and grid[y][x] != "#":
                count += 1
            for i in range(start, x+1):
                scores[y][i][0] = count
            count = 0
            start = x + 1
        else:
            count += 1

for x in range(W):
    start = 0
    count = 0
    for y in range(H):
        if grid[y][x] == "#" or y == H-1:
            if y == H-1 and grid[y][x] != "#":
                count += 1
            for i in range(start, y+1):
                scores[i][x][1] = count
            count = 0
            start = y + 1
        else:
            count += 1

# print(scores)
ans = 0
for y in range(H):
    for x in range(W):
        ans = max(ans, sum(scores[y][x])-1)
print(ans)

### FIXED CODE ###

import sys

H, W = map(int, sys.stdin.readline().strip().split())
grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

# (x, y)のx, y方向のscore [a, b]
scores_y = [[0 for _ in range(W)] for _ in range(H)]
scores_x = [[0 for _ in range(W)] for _ in range(H)]
for y in range(H):
    start = 0
    count = 0
    for x in range(W):
        if grid[y][x] == "#" or x == W-1:
            if x == W-1 and grid[y][x] != "#":
                count += 1
            for i in range(start, x+1):
                scores_x[y][i] = count
            count = 0
            start = x + 1
        else:
            count += 1

for x in range(W):
    start = 0
    count = 0
    for y in range(H):
        if grid[y][x] == "#" or y == H-1:
            if y == H-1 and grid[y][x] != "#":
                count += 1
            for i in range(start, y+1):
                scores_y[i][x] = count
            count = 0
            start = y + 1
        else:
            count += 1

# print(scores)
ans = 0
for y in range(H):
    for x in range(W):
        ans = max(ans, scores_x[y][x] + scores_y[y][x] - 1)
print(ans)
### BUGGY CODE ###

a, b, x = map(int, input().split())

# print(a)
# print(b)
# print(x)

count = 0
for i in range(a, b + 1):
    # print(i)
    
    if i % x == 0:
        count += 1
        
print(count)

### FIXED CODE ###

a, b, x = map(int, input().split())

# print(a)
# print(b)
# print(x)

# count = 0
# for i in range(a, b + 1):
#     # print(i)
    
#     if i % x == 0:
#         count += 1
        
# print(count)

def f(n):
    if n == -1:
        return 0
    else:
        return (n // x) + 1

# print(int((a -1) / x) + 1)
# print(int(b / x))

# print(f(b))
# print(f(a - 1))
print(f(b) - f(a - 1))
### BUGGY CODE ###

n = int(input())
p = 1
for i in range(1, n + 1):
  p *= i
print(p % (10 ** 9 + 7))

### FIXED CODE ###

n = int(input())
x, i = 1, 1
while i <= n:
  x = (x * i) % (10 ** 9 + 7)
  i += 1
print(x)
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    count2 = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        tmp = count
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count == tmp : count2 += 1
        if count2 > 10 : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.97
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

h,w,m=map(int,input().split())
B=[[] for i in range(h)]
H=[0]*h
W=[0]*w
for i in range(m):
    p,q=map(int,input().split())
    B[p-1].append(q-1)
    H[p-1]+=1
    W[q-1]+=1
mH=max(H)
mW=max(W)
CH=[]
for i in range(h):
    if H[i]==mH:
        CH.append(i)
CW=[]
for i in range(w):
    if W[i]==mW:
        CW.append(i)
flag=0
if len(CH)*len(CW)>m:
    flag=1
else:
    for ch in CH:
        for cw in CW:
            if cw in B[ch]:
                continue
            else:
                flag=1
                break
if flag:
    print(mH+mW)
else:
    print(mH+mW-1)

### FIXED CODE ###

h,w,m=map(int,input().split())
B=[[] for i in range(h)]
H=[0]*h
W=[0]*w
for i in range(m):
    p,q=map(int,input().split())
    B[p-1].append(q-1)
    H[p-1]+=1
    W[q-1]+=1
mH=max(H)
mW=max(W)
CH=[]
for i in range(h):
    if H[i]==mH:
        CH.append(i)
CW=[]
for i in range(w):
    if W[i]==mW:
        CW.append(i)
CW=set(CW)
flag=0
if len(CH)*len(CW)>m:
    flag=1
else:
    for ch in CH:
        b=set(B[ch])
        if CW<=b:
            continue
        else:
            flag=1
            break
if flag:
    print(mH+mW)
else:
    print(mH+mW-1)
### BUGGY CODE ###

n, m = map(int, input().split(" "))
path = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split(" "))
    path[u-1].append(v)

s, g = map(int, input().split(" "))
ifReached = [False for _ in range(n)]

def indicate3(start,path):
    for _ in range(3):
        next = []
        for position in start:
            for next_position in path[position-1]:
                next.append(next_position)
        start = next
    return start

stack = [s]
count = 0
unreachable = False
while True:
    n_stack = list(set(indicate3(stack,path)))
    diffcount = 0
    for position in n_stack:
        if ifReached[position-1] == False:
            ifReached[position-1] = True
            diffcount += 1

    if diffcount == 0:
        print(-1)
        break

    if g in n_stack:
        count += 1
        print(count)
        break
    else:
        if n_stack == stack:
            print(-1)
            break
        else:
            count += 1
            if unreachable == True:
                print(-1)
                break
    stack = n_stack

### FIXED CODE ###

n, m = map(int, input().split(" "))
path = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split(" "))
    path[u-1].append(v)

s, g = map(int, input().split(" "))
ifReached = [False for _ in range(n)]

def indicate3(start,path):
    for _ in range(3):
        next = []
        for position in start:
            for next_position in path[position-1]:
                next.append(next_position)
        start = list(set(next))
    return start

stack = [s]
ifReached[s-1] = True
count = 0
while True:
    n_stack = list(set(indicate3(stack,path)))

    tmp_stack = []
    for position in n_stack:
        if ifReached[position-1] == False:
            tmp_stack.append(position)
            ifReached[position-1] = True

    if len(tmp_stack) == 0:
        print(-1)
        break

    count += 1
    if g in tmp_stack:
        print(count)
        break
    stack = tmp_stack
### BUGGY CODE ###

N, K = map(int, input().split())
nums = list(map(int, input().split()))
dp = [0] * (N+1)
dp[0] = 0
for i in range(1, N):
  min_c = 10**10
  for j in range(1, min(i, K)+1):
    min_c = min(min_c, dp[i-j]+abs(nums[i-j]-nums[i]))
  dp[i] = min_c
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
nums = list(map(int, input().split()))
dp = [0] * (N+1)
dp[0] = 0
for i in range(1, N):
  min_c = 10**10
  for j in range(1, min(i, K)+1):
    min_c = min(min_c, dp[i-j]+abs(nums[i-j]-nums[i]))
  dp[i] = min_c
print(dp[N-1])
### BUGGY CODE ###

import numpy as np
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7
def lcm (x,y):
  return (x//gcd(x,y))*y

p = A[0]
for a in A[1:]:
  p = lcm(p, a)

ans = 0
for a in A:
  ans += p//a
print(ans % MOD)


### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7
def lcm (x,y):
  return x*y//gcd(x,y)
 
p = A[0]
for a in A[1:]:
  p = lcm(p, a)
 
ans = 0
for a in A:
  ans += p//a
print(ans % MOD)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
ans = 0

for i in range(int(n/b)+1):
    for j in range(int(n/g)+1):
        for k in range(int(n/r)+1):
            cheak = r*k + g*j + b*i
            if cheak == n:
                ans += 1
print(ans)

### FIXED CODE ###

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

r, g, b, n = map(int, read().split())
cnt = 0
for i in range(n + 1):
    for j in range(n + 1):
        check = n - (r * i + g * j)
        if check >= 0:
            if check % b == 0:
                cnt += 1
        else:
            break
print(cnt)
### BUGGY CODE ###

N = int(input())
A_list = [int(_)%(10**9+7) for _ in input().split()]

ans = 0
for i in range(len(A_list)):
    if i <= N-1:
        for j in range(i + 1, N):
            ans += A_list[i]*A_list[j]
            ans = ans%(10**9+7)
print(ans)

### FIXED CODE ###

N = int(input())
A_list = [int(_) for _ in input().split()]

c = 10**9+7


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


inv = modinv(2, c)

sum_of_a = sum(A_list) % c
sum_of_sq_a = sum([i**2 for i in A_list]) % c

ans = (sum_of_a**2 % c - sum_of_sq_a)*inv %c

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

def gcd(m,n):
    while (m % n != 0):
        temp = n
        n = m % n
        m = temp
    return(n)


k = int(input())
s = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            s += gcd(a,gcd(b,c))
print(s)

### FIXED CODE ###

def gcd(m,n):
    while (m % n != 0):
        n,m = m%n,n
    return(n)


k = int(input())
s = 0
for a in range(1,k+1):
    for b in range(a,k+1):
        t = gcd(a,b)
        for c in range(b,k+1):
            v = gcd(t,c)
            l = len(set([a,b,c]))
            if(l == 1):s += v
            elif(l == 2):s += v * 3
            else:s += v * 6
print(s)
### BUGGY CODE ###

from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 7)


def LI(): return list(map(int, stdin.readline().split()))


inf = 1000000007


def main():
    N, K = LI()
    graph = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = LI()
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)

    stack = [0]
    ans = 1
    done = [False] * N
    while len(stack) > 0:
        now = stack.pop(0)
        done[now] = True
        cnt = 0
        for x in graph[now]:
            if not done[x]:
                cnt += 1
                stack.append(x)
        if now == 0:
            for i in range(cnt):
                ans = (K - 1 - i) * ans % inf
        else:
            for i in range(cnt):
                ans = (K - 2 - i) * ans % inf
    print(ans * K % inf)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

S = list(input())
S.reverse()
N = len(S)
mod = 10 ** 9 + 7
ans = [[0 for r in range(13)] for n in range(N)]
if S[0] == '?':
    ans[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
else:
    ans[0][int(S[0])] = 1
for n in range(1, N):
    if S[n] == '?':
        ans[n] = [sum([ans[n-1][(r-(d*(10**n) % 13)) % 13]
                       for d in range(10)]) % mod for r in range(13)]
        # for r in range(13):
        #     count = 0
        #     for d in range(10):
        #         r1 = d * (10 ** n) % 13
        #         r0 = (r - r1) % 13
        #         count += ans[n - 1][r0] % mod
        #     ans[n][r] = count % mod
    else:
        ans[n] = [ans[n-1][(r-(int(S[n])*(10**n) % 13)) % 13]
                  for r in range(13)]
        # for r in range(13):
        #     d = int(S[n])
        #     r1 = d * (10 ** n) % 13
        #     r0 = (r - r1) % 13
        #     ans[n][r] = ans[n-1][r0] % mod
print(ans[N-1][5])


### FIXED CODE ###

S = list(input())
S.reverse()
N = len(S)
mod = 10**9+7
dp = [[0 for r in range(13)] for n in range(N+1)]
dp[0][0] = 1
lookup = [[0 for d in range(10)] for n in range(N)]
for n in range(N):
    for d in range(10):
        lookup[n][d] = d*pow(10, n, 13) % 13
for n in range(1, N+1):
    if S[n-1] == '?':
        for d in range(10):
            for r in range(13):
                dp[n][(r+lookup[n-1][d]) % 13] += dp[n-1][r] % mod
    else:
        for r in range(13):
            dp[n][(r+lookup[n-1][int(S[n-1])]) % 13] += dp[n-1][r] % mod
print(dp[-1][5] % mod)
### BUGGY CODE ###

h, w = map(int, input().split())
c = [list(map(ord, input())) for i in range(h)]
INF = 10 ** 9


ans = 0
dq = [[0] * (h + 1) for i in range(h + 1)]
dp = [[INF] * (h + 1) for i in range(h + 1)]
for wi in range(w - 1):
    for diff in range(h + 1):
        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            cnt += (c[i][wi] == c[i + diff][wi + 1])
        dq[0 + diff][0] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            cnt -= (c[h - i - 1 - diff][wi] == c[h - i - 1][wi + 1])
            dq[i + 1 + diff][i + 1] = cnt

        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            cnt += (c[i + diff][wi] == c[i][wi + 1])
        dq[0][0 + diff] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            cnt -= (c[h - i - 1 - diff][wi + 1] == c[h - i - 1][wi])
            dq[i + 1][i + 1 + diff] = cnt
            
    for i in range(h + 1):
        for j in range(h + 1):
            dp[i][j] = INF
    dp[0][0] = 0
    for i in range(h + 1):
        for j in range(h + 1):
            if i + 1 < h + 1:
                dp[i + 1][j] = min(dp[i][j] + dq[i][j], dp[i + 1][j])
            if j + 1 < h + 1:
                dp[i][j + 1] = min(dp[i][j] + dq[i][j], dp[i][j + 1])
    ans += dp[-1][-1]

print(ans)
    

### FIXED CODE ###

def solve(k):
    dp = [[0] * (h + 1) for i in range(h + 1)]
    for i in range(h):
        for diff in range(h - i):
            dp[i + 1][i + 1 + diff] = dp[i][i + diff] + (s[i + diff][k] == s[i][k + 1])
            dp[i + 1 + diff][i + 1] = dp[i + diff][i] + (s[i][k] == s[i + diff][k + 1])

    dq = [[INF] * (h + 1) for i in range(h + 1)]
    dq[0][0] = 0
    for i in range(h):
        dq[i + 1][0] = dq[i][0] + dp[h - i][h]
        dq[0][i + 1] = dq[0][i] + dp[h][h - i]  
    for i in range(h):
        for j in range(h):
            dq[i + 1][j + 1] = min(dq[i + 1][j] + dp[h - (i + 1)][h - j],
                                   dq[i][j + 1] + dp[h - i][h - (j + 1)])

    return dq[h][h]


h, w = map(int, input().split())
s = [input() for i in range(h)]
INF = 10 ** 5
OFFSET = 500

ans = 0
for i in range(w - 1):
    ans += solve(i)
    
print(ans)
### BUGGY CODE ###

import sys, heapq, bisect, math, fractions
from collections import deque
from collections import Counter
from collections import OrderedDict

N = int(input())

left = 0
right = N - 1
mid = 0
ll = True
rr = True

for _ in range(20):
    if ll:
        print(left, flush=True)
        l = input()
        if l == "Vacant":
            exit()
        ll = not ll
    if rr:
        print(right, flush=True)
        r = input()
        if r == "Vacant":
            exit()
        rr = not rr

    mid = (r + l) // 2
    print(mid, flush=True)
    m = input()
    if m == "Vacant":
        exit()

    if (mid - left) % 2 == 0 and l != m:
        right = mid - 1
        rr = True
    elif (right - mid) % 2 == 1 and m == r:
        left = mid + 1
        ll = True

### FIXED CODE ###

import sys, heapq, bisect, math, fractions
from collections import deque
from collections import Counter
from collections import OrderedDict

N = int(input())

left = 0
right = N - 1
mid = 0

print(left, flush=True)
l = input()
if l == "Vacant":
    exit()
    
print(right, flush=True)
r = input()
if r == "Vacant":
    exit()

while left + 1 != right:
    mid = (right + left) // 2
    print(mid, flush=True)
    m = input()
    if m == "Vacant":
        exit()
        
    if ((mid - left) % 2 == 0 and l != m) or ((mid - left) % 2 == 1 and l == m):
        right = mid
        r = m
    else:
        left = mid
        l = m
### BUGGY CODE ###

n,m = map(int, input().split())
p = [0] * m
s = [0] * m
for i in range(m):
    p[i],s[i] = map(str,input().split())
    p[i] = int(p[i])

ac = []
for i in range(m):
    if s[i] == 'AC':
        ac.append(p[i])

ac = list(set(ac))

ans_ng = 0
for id in ac:
    ng = 0
    for j in range(m):
        if p[j] == id and s[j] == 'WA':
            ng += 1
        elif p[j] == id and s[j] == 'AC':
            break
    ans_ng += ng
            


print(len(ac),ans_ng)


### FIXED CODE ###

n,m = map(int, input().split())
p = [0] * m
s = [0] * m
for i in range(m):
    p[i],s[i] = map(str,input().split())
    p[i] = int(p[i])

ac = [0] * (n+1)
wa = [0] * (n+1)
for i in range(m):
    if s[i] == 'WA':
        if ac[p[i]] == 0:
            wa[p[i]] += 1
        else:
            pass
    if s[i] == 'AC':
        ac[p[i]] = 1

ac_num = 0
for i in range(len(ac)):
    if ac[i] != 0:
        ac_num += 1
ng = 0
for i in range(len(wa)):
    if ac[i] != 0:
        ng += wa[i]
            
print(ac_num,ng)
### BUGGY CODE ###

N = map(int, input().split())
l = list(map(int, input().split()))
from collections import deque


l = deque(l)

count=0
for i in range(len(l)-1):
    if l[i] >l[i+1]:
        c=l[i] -l[i+1]
        l[i+1]+=c
        count+=c

print(count)

### FIXED CODE ###

N = map(int, input().split())
l = list(map(int, input().split()))
from collections import deque


l = deque(l)

count=0
for i in range(len(l)-1):
    if l[i] >l[i+1]:
        c=l[i] -l[i+1]
        l[i+1]+=c
        count+=c

print(count)
### BUGGY CODE ###

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

    mul = 1
    for a in A:
        mul *= a

    if mul > 10 ** 18:
        print(-1)
        return

    print(mul)

main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    for a in A:
        if a == 0:
            print(0)
            return

    mul = 1
    for a in A:
        mul *= a
        if mul > 10 ** 18:
            print(-1)
            return

    print(mul)

main()
### BUGGY CODE ###

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

for m_i in range(m):
  
  l,r = map(int, input().split())
  if m_i==0:
    ans = set(range(l, r+1))
  else:
    ans &= set(range(l, r+1))
    
print(len(ans))

### FIXED CODE ###

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

L = []
R = []

for _ in range(m):
  l,r = map(int, input().split())
  L.append(l)
  R.append(r)
    
print(min(R)-max(L)+1 if min(R)-max(L)>=0 else 0)
### BUGGY CODE ###

from collections import Counter

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

dic = Counter(l)
ans = 0
kv = dic.items()
kv = sorted(kv, key=lambda x: x[1])
while len(kv) > k:
    ans += kv[0][1]
    del kv[0]

print(ans)

### FIXED CODE ###

from collections import Counter

n, k = map(int, input().split())
dic = Counter(list(map(int, input().split())))
kv = dic.items()
kv = sorted(kv, key=lambda x: x[1])
ans = 0
cnt = 0
while len(kv)-cnt > k:
    ans += kv[cnt][1]
    cnt+=1
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

from queue import deque

def main():
  h, w = map(int, input().split())
  grids = [list(input().strip()) for _ in range(h)]
  dq = deque()
  for i in range(h):
    for j in range(w):
      if grids[i][j] == '#':
        dq.append((0, i, j))
  
  mcnt = -1
  while dq:
    cnt, i, j = dq.popleft()
    for dx, dy in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
      if 0 <= i+dx < h and 0 <= j+dy < w and grids[i+dx][j+dy] == '.':
        grids[i+dx][j+dy] = '#'
        dq.append((cnt+1, i+dx, j+dy))
  print(cnt)
  
if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

from queue import deque

def main():
  h, w = map(int, input().split())
  grids = [False] * (w * h)
  dq = deque()
  for i in range(h):
    for j, c in enumerate(list(input().strip())):
      if c == '#':
        grids[i*w + j] = True
        dq.append((0, i, j))
  
  while dq:
    cnt, i, j = dq.popleft()
    for dx, dy in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
      if 0 <= i+dx < h and 0 <= j+dy < w and not grids[(i+dx)*w + (j+dy)]:
        grids[(i+dx)*w + (j+dy)] = True
        dq.append((cnt+1, i+dx, j+dy))
  print(cnt)
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

from itertools import permutations
N,M,R = list(map(int,input().split()))
r = list(map(int,input().split()))
r = [i-1 for i in r]
ABC = [[float('inf') for i in range(N)]for j in range(N)]
for i in range(N):
    ABC[i][i] = 0
for i in range(M):
    a,b,c = list(map(int,input().split()))
    a -= 1
    b -= 1
    ABC[a][b] = c
    ABC[b][a] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            ABC[i][j] = min(ABC[i][j],ABC[i][k]+ABC[k][j])
ans = float('inf')
for i in permutations(r):
    cost = 0
    now = i[0]
    for j in range(1,len(i)):
        cost += ABC[now][i[j]]
        now = i[j]
    ans = min(ans,cost)
print(ans)

### FIXED CODE ###

from itertools import permutations
N,M,R = list(map(int,input().split()))
r = list(map(int,input().split()))
r = [i-1 for i in r]
ABC = [[float('inf') for i in range(N)]for j in range(N)]
for i in range(N):
    ABC[i][i] = 0
for i in range(M):
    a,b,c = list(map(int,input().split()))
    a -= 1
    b -= 1
    ABC[a][b] = c
    ABC[b][a] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            ABC[i][j] = min(ABC[i][j],ABC[i][k]+ABC[k][j])
ans = float('inf')
for i in permutations(r):
    cost = 0
    now = i[0]
    for j in range(1,len(i)):
        cost += ABC[now][i[j]]
        now = i[j]
    ans = min(ans,cost)
print(ans)