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

MOD = 10 ** 9 + 7

N, M = map(int, input().strip().split())
S = [int(i) for i in input().strip().split()]
T = [int(i) for i in input().strip().split()]

sdp = [[0] * (len(T)) for _ in range(len(S))]

for i, s in enumerate(S):
  for j, t in enumerate(T):
    sdp[i][j] = 1 if s == t else 0
    if i > 0: sdp[i][j] += sdp[i - 1][j]
    if j > 0: sdp[i][j] += sdp[i][j - 1]
    if s != t and i > 0 and j > 0: sdp[i][j] -= sdp[i - 1][j - 1]
    sdp[i][j] %= MOD

print(sdp[-1][-1] + 1)
# for row in sdp:
#  print(('{: 4d} ' * len(row)).format(*row))
## print(sdp)

### FIXED CODE ###

MOD = 10 ** 9 + 7


def main(S, T):
  l = len(T) + 1
  dp = [0] * l
  # sdp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

  # for i, s in enumerate(S):
  #  for j, t in enumerate(T):
  #    v = sdp[i][j + 1] + sdp[i + 1][j] + (1 if s == t else -sdp[i][j])
  #    sdp[i + 1][j + 1] = v % MOD
  for i, s in enumerate(S):
    tmp = [0] * l
    for j, t in enumerate(T):
      v = dp[j + 1] + tmp[j] + (1 if s == t else -dp[j])
      tmp[j + 1] = v % MOD
    dp = tmp

  # return (sdp[-1][-1] + 1)
  return dp[-1] + 1


if __name__ == '__main__':
  if True:
    _, _ = map(int, input().strip().split())
    S = input().strip().split()
    T = input().strip().split()
  else:
    S = range(1000)
    T = range(1000)
  print(main(S, T))
### BUGGY CODE ###

from collections import deque
import sys
N = int(input().strip("\n"))
A = [list(map(lambda x :int(x)-1, input().split())) for _ in range(N)]

# 対戦カード (インデックス0>インデックス[1]だけ使う)
all_patterns = [[[] for _ in range(N)] for _ in range(N)]
lines_to_here = [[0 for _ in range(N)] for _ in range(N)]

for i in range(len(A)):
    for j in range(len(A[i])-1):
        playerA = i
        playerB = A[i][j]
        if playerA < playerB:
            playerA, playerB = playerB, playerA
        next_playerA = i
        next_playerB = A[i][j+1]
        if next_playerA < next_playerB:
            next_playerA, next_playerB = next_playerB, next_playerA
        
        all_patterns[playerA][playerB].append([next_playerA,next_playerB])
        lines_to_here[next_playerA][next_playerB] += 1

next_out = deque()
for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] == 0:
            next_out.append([i,j])

if len(next_out) == 0:
    print(-1)
    sys.exit()

indexin_topological_sorted = [[0 for _ in range(N)] for _ in range(N)]

# topological sort
topological_sorted = []
while len(next_out) > 0:
    added = next_out.pop()
    topological_sorted.append(added)
    indexin_topological_sorted[added[0]][added[1]] = len(topological_sorted)-1
    for direction in all_patterns[added[0]][added[1]]:
        lines_to_here[direction[0]][direction[1]]-=1
        if lines_to_here[direction[0]][direction[1]] == 0:
            next_out.append(direction)

# if there is closed circuit, number remain(not 0 exists)
for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] > 0:
            print(-1) 
            sys.exit()

costs = [0 for _ in range(len(topological_sorted))]

max_cost = 0
for i in range(len(topological_sorted)):
    processing = topological_sorted[i]
    now_cost = costs[i]
    for direction in all_patterns[processing[0]][processing[1]]:
        direction_in_topological_sorted = indexin_topological_sorted[direction[0]][direction[1]]        
        costs[direction_in_topological_sorted] = max(1+now_cost,costs[direction_in_topological_sorted])
        max_cost = max(max_cost,costs[direction_in_topological_sorted])
print(max_cost+1)


### FIXED CODE ###

from collections import deque

N = int(input().strip("\n"))
ALL = N*(N-1)//2
A = [deque(list(map(lambda x :int(x)-1, input().split()))) for _ in range(N)]

day = 0
candidates = set(range(N))
while len(candidates)>0:
    day += 1
    nextday = set()
    checked = set()
    #print(candidates)
    for candidate in candidates:
        if len(A[candidate]) == 0:
            continue
        if candidate in checked:
            continue
        opponent = A[candidate][0]
        if opponent in checked:
            continue
        if A[opponent][0] == candidate:
            A[opponent].popleft()
            A[candidate].popleft()
            nextday.add(candidate)
            nextday.add(opponent)
            checked.add(candidate)
            checked.add(opponent)
    candidates = nextday

for p in A:
    if len(p) > 0:
        print(-1)
        break
else:
    print(day-1)
### BUGGY CODE ###

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

score = [1 for _ in range(n-k+1)]
temp = 1
for i in range(k):
    temp *= a[i]
score[0] = temp
for j in range(1,n-k+1):
    score[j] = score[j-1]*a[j+k-1]//a[j-1]

#print(score)
for i in range(1,n-k+1):
    if score[i-1] < score[i]:
        print('Yes')
    else:
        print('No')
    

### FIXED CODE ###

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

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

S = input()
C = [1 for _ in range(len(S))]
b1 = C[::]
b2 = C[::]
for n in range(10**5+5):
    C = [0 for _ in range(len(S))]
    for i,s in enumerate(S):
        if s == "R":
            C[i+1] += b1[i]
        else:
            C[i-1] += b1[i]
    if C == b2:
        if n%2==1:
            print(*C)
        else:
            print(*b1)
        break
    b2 = b1[::]
    b1 = C[::]

### FIXED CODE ###

S = input()
C = [0 for _ in range(len(S))]
b = "R"
l,r = 0,0
for i,s in enumerate(S):
    if s != b and s == "L":
        #print("ST",i)
        for j in range(1,i+1):
            #print("#l",i,j,S[i-j])
            if S[i-j] == "L":
                l = j - 1
                break
        else:
            l = j
        j = 0
        for j in range(1,len(S)-i):
            #print("#r",i,j,S[i+j])
            if S[i+j] == "R":
                r = j
                break
        else:
            r = j + 1
        #print(i,l,r)
        C[i] = (r+1)//2 + l//2
        C[i-1] = r//2 + (l+1)//2
    b = s
print(*C)
### BUGGY CODE ###

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

import sys

def main():
    c = tuple(tuple(map(int, line.split())) for line in sys.stdin.readlines())
    for i in range(-100, 101):
        b = [c[0][0] - i]
        for j in range(-100, 101):
            b.append(c[1][1] - j)
            for k in range(-100, 101):
                b.append(c[2][2] - k)
                a = (i, j, k)
                flg = False
                for l in range(3):
                    for m in range(3):
                        if l != m and a[l] + b[m] != c[l][m]:
                            flg = True
                            break
                    if flg == True:
                        break
                else:
                    print('Yes')
                    sys.exit()
    else:
        print('No')

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

import sys

def main():
    c = tuple(tuple(map(int, line.split())) for line in sys.stdin.readlines())
    csum = sum((sum(ci) for ci in c))
    trace = sum((cij for i, ci in enumerate(c) for j, cij in enumerate(ci) if i == j))
    if csum == 3 * trace:
        print('Yes')
    else:
        print('No')
if __name__ == '__main__':
    main()
### BUGGY CODE ###


H,W,D=map(int,input().split())

dic={}
A=[]
for h in range(H):
    A.append(list(map(int,input().split())))
    for w in range(W):
        dic[A[h][w]]=[h,w]

Q=int(input())

c=[-1]*(H*W+1)

def rec(n):
    if c[n]!=-1:
        return c[n]
    y,x=dic[n]
    ny,nx=dic[n+D]
    ret=abs(y-ny)+abs(x-nx)
    c[n]=ret
    return ret

for i in range(Q):
    L,R=map(int,input().split())
    N=(R-L)//D
    ans=0
    for j in range(N):
        ans+=rec(L+D*j)
    print(ans)

### FIXED CODE ###

H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

S=[0]*(H*W)
for d in range(D):
    tmp=0
    now=d+1
    while now+D<=H*W:
        nowh,noww=pos[now]
        newh,neww=pos[now+D]
        tmp+=abs(nowh-newh)+abs(noww-neww)
        S[now+D-1]=tmp
        now+=D

Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    ans=S[R-1]-S[L-1]
    print(ans)
### BUGGY CODE ###

import sys
class Heap:
    def __init__(self):
        self.heap = [None]*1000000
        self.root = 0
        self.size = 0
    
    def push(self, a:int):
        self.heap[self.size] = a
        b = self.size
        while b != 0 and self.heap[(b - 1) //2] < self.heap[b]:
            c = self.heap[(b - 1) //2]
            self.heap[(b - 1) //2] = self.heap[b]
            self.heap[b] = c
            b = (b - 1) //2
        self.size += 1
    
    def pop(self):
        a = self.heap[0]
        b = 0
        self.heap[b] = self.heap[self.size - 1]
        self.heap[self.size] = None
        self.size -= 1
        while (self.heap[b*2 + 1] is not None and self.heap[b] < self.heap[b*2 + 1]) or (self.heap[b*2 + 2] is not None and self.heap[b] < self.heap[b*2 + 2]):
            if self.heap[b*2 + 2] > self.heap[b*2 + 1]:
                c = self.heap[b]
                self.heap[b] = self.heap[b*2 + 2]
                self.heap[b*2 + 2] = c
                b = b*2 + 2
            else:
                c = self.heap[b]
                self.heap[b] = self.heap[b*2 + 1]
                self.heap[b*2 + 1] = c
                b = b*2 + 1
        return a
def main(): 
    x, y, A, B, C = map(int, input().split())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))
    r = list(map(int, input().split()))
    pq = Heap()
    p.sort()
    q.sort()
    for i in range(x):
        pq.push(p[len(p) - 1 - i])
    for i in range(y):
        pq.push(q[len(q) - 1 - i])
    for i in range(len(r)):
        pq.push(r[i])
    ans = 0
    for i in range(x + y):
        ans += pq.pop()
    print(ans)

main()

### FIXED CODE ###

import sys
import heapq
def main(): 
    x, y, A, B, C = map(int, input().split())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))
    r = list(map(int, input().split()))
    pq = []
    heapq.heapify(pq)
    p.sort()
    q.sort()
    for i in range(x):
        heapq.heappush(pq,-1*p[len(p) - 1 - i])
    for i in range(y):
        heapq.heappush(pq, -1*q[len(q) - 1 - i])
    for i in range(len(r)):
        heapq.heappush(pq, -1*r[i])
    ans = 0
    for i in range(x + y):
        ans += -1*heapq.heappop(pq)
    print(ans)

main()
### BUGGY CODE ###

from functools import reduce

n = int(input())  # nは入力回数
l = [int(x) for x in list(str(n))]

num=len(l)
count=0

for i in range(num-3): 
    for j in range(3,num):
        if i>=j or j-i<3:
            pass
        else:
            new_n = int(reduce(lambda x, y: x + y, [str(x) for x in l[i:j+1]]))
            if new_n%2019==0:
              count=count+1  
print(count)
    

### FIXED CODE ###

s=input()
s=s[::-1]
n=len(s)
 
count=[0]*2019
count[0]=1
num,d=0,1
 
for i in s:
  num+=int(i)*d
  num%=2019
  d*=10
  d%=2019
  count[num]+=1
 
ans=0
for i in count:
  ans+=i*(i-1)//2
  
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
print = sys.stdout.write

def bit_add(arr, n, i, x):
    while i <= n:
        arr[i] += x
        i += i & -i

def bit_sum(arr, i):
    result = 0
    while i > 0:
        result += arr[i]
        i ^= i & -i
    return result

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

L, R = [], []
for _ in range(Q):
    l, r = map(int, input().split())
    L.append(l-1);R.append(r-1)
    
just_left = {}
segments = []
for i in range(N):
    c = C[i]
    if c in just_left:
        segments.append((i, 0, just_left[c], 0))
    just_left[c] = i

for i in range(Q):
    segments.append((R[i], 1, L[i], i))

segments.sort()
bit = [0] * (N+2)
ans = [0] * Q

for r, tp, l, i in segments:
    if tp == 0:
        bit_add(bit, N + 2, l + 2, 1)
    else:
        base = r - l + 1
        ans[i] = base - (bit_sum(bit, r + 2) - bit_sum(bit, l + 1))

print("\n".join(map(str,ans)))

### FIXED CODE ###

import numpy as np

def solve(inp):
    def bit_add(arr, n, i, x):
        while i <= n:
            arr[i] += x
            i += i & -i

    def bit_sum(arr, i):
        result = 0
        while i > 0:
            result += arr[i]
            i ^= i & -i
        return result

    N, Q = inp[:2]
    C = inp[2: 2+N]
    L, R = inp[2+N::2] - 1, inp[3+N::2] - 1

    just_left = {}
    segments = []
    for i in range(N):
        c = C[i]
        if c in just_left:
            segments.append((i, 0, just_left[c], 0))
        just_left[c] = i

    for i in range(Q):
        segments.append((R[i], 1, L[i], i))

    segments.sort()
    bit = np.zeros(N + 2, dtype=np.int64)
    ans = np.zeros(Q, dtype=np.int64)

    for r, tp, l, i in segments:
        if tp == 0:
            bit_add(bit, N + 2, l + 2, 1)
        else:
            base = r - l + 1
            ans[i] = base - (bit_sum(bit, r + 2) - bit_sum(bit, l + 1))

    return ans

def main():
    inp = np.fromstring(open(0).read(), dtype=np.int64, sep=' ')
    ans = solve(inp)
    print("\n".join(map(str,ans)))
    

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

for v in range(max(A) + K, 0, -1):
    sum_m = []
    for a in A:
        sum_m.append(a % v)
    if sum(sum_m) % v == 0:
        if sum(sum_m) - max(sum_m) <= K:
            print(v)
            break


### FIXED CODE ###

import sys
input = sys.stdin.readline

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


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    # divisors.sort()
    return divisors


d_cand = make_divisors(sum(A))
d_cand.sort()
d_cand.reverse()

for d in d_cand:
    r = [a % d for a in A]
    rp_sum = sum(r)
    rm_sum = 0
    if rp_sum % d != 0:
        continue
    r.sort()

    for i in range(N):
        # index i まで r-, i+1から r+
        rp_sum -= r[i]
        rm_sum += r[i]

        n_min = max(0, -(rm_sum + rp_sum) / d + (N - i - 1))
        n_max = (K - rm_sum) / d
        if n_min <= n_max and (n_min % 1 == 0 or n_max % 1 == 0 or int(n_min) != int(n_max)):
            print(d)
            break
    else:
        continue
    break
### BUGGY CODE ###

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

dp = [10**9+1]*n
dp[0] = 0
dp[1] = dp[0] + abs(h[1]-h[0])

for i in range(2, n): 
    dp[i] = min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1, min(k, i)+1)])

print(dp[n-1])

### FIXED CODE ###

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

dp = [10**9+1]*n
dp[0] = 0
dp[1] = dp[0] + abs(h[1]-h[0])

for i in range(2, n): 
    dp[i] = min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1, min(k, i)+1)])

print(dp[n-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def toId(i, j):
    pair = A[i][j]
    if i > pair:
        i, pair = pair, i
    return ids[i][pair]

def dfs(x):
    if dp[x] != -1:
        if done[x]:
            return dp[x]
        else:
            return -1
    dp[x] = 1
    for y in G[x]:
        res = dfs(y)
        if res == -1:
            return -1
        dp[x] = max(dp[x], dfs(y)+1)
    done[x] = True
    return dp[x]

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
ids = [[0]*N for i in range(N)]
num = 0
for i in range(N):
    for j in range(N):
        if i < j:
            ids[i][j] = num
            num += 1
allv = N*N
G = [[] for i in range(allv)]
for i in range(N):
    for j in range(N-2):
        G[toId(i,j+1)].append(toId(i,j))
dp = [-1 for i in range(allv)]
done = [False for i in range(allv)]
ans = 0
for i in range(allv):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, dfs(i))
print(ans)


### FIXED CODE ###

N = int(input())
A = [list(map(lambda n: int(n)-1, input().split())) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
    done = {}
    que2 = []
    for n in que:
        if done.get(n):
            continue
        pair = A[n][cur[n]]
        if done.get(pair):
            continue
        if n == A[pair][cur[pair]]:
            cur[n] += 1
            cur[pair] += 1
            done[n] = True
            done[pair] = True
            if cur[n] < N-1:
                que2.append(n)
            if cur[pair] < N-1:
                que2.append(pair)
    if len(done) > 0:
        ans += 1
    que = que2
ok = True
for i in range(N):
    if cur[i] < N-1:
        ok = False
if ok:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

n, k = map(int, input().split())
a = [int(x)-1 for x in input().split()]

inds = {}
y = [0]*n

for i in range(n):
    if a[i] in inds:
        y[inds[a[i]][-1]] = i+1 - inds[a[i]][-1]
        inds[a[i]].append(i)
    else:
        inds[a[i]] = [i]

for lst in inds.values():
    y[lst[-1]] = n+lst[0]+1 - lst[-1]

length = (n*k).bit_length()

db = {0: y}
for m in range(length):
    db[m+1] = [db[m][i] + db[m][(i+db[m][i]) % n] for i in range(n)]

cur = 0
i = length

while cur < n*k:
    while i > -1 and cur + db[i][cur % n] > n*k:
        i -= 1
    if i == -1:
        break
    cur = cur + db[i][cur % n]

ans = []
while cur < n*k:
    if cur + db[0][cur % n] > n*k:
        ans.append(cur)
        cur += 1
    elif cur + db[0][cur % n] == n*k:
        break
    else:
        cur = cur + db[0][cur % n]

print(*map(lambda x: a[x % n]+1, ans))


### FIXED CODE ###

from bisect import bisect_right
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

d = {}
for i in range(n):
    if a[i] in d:
        d[a[i]].append(i)
    else:
        d[a[i]] = [i]


def simulate(k):
    if k == 0:
        return 0, []
    lap = 1
    res = [0]
    while True:
        s = res.pop()
        nxt = d[a[s]][bisect_right(d[a[s]], s) % len(d[a[s]])] + 1
        if nxt == n:
            if lap == k and s == n-1:
                res.append(s)
            if s == n-1:
                lap += 1
            return lap, res
        elif nxt <= s+1:
            if lap == k:
                res.append(s)
                if s == n-1:
                    return lap, res
                res.append(s+1)
                if s+1 == n-1:
                    return lap, res
            else:
                res.append(nxt)
                lap += 1
        else:  # s+1 < nxt
            s = nxt
            res.append(s)
    return 0


period, ans = simulate(k)

if period != k:
    lap, ans = simulate(k % period)

print(*[a[x] for x in ans])
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
ans = 0
if N % 2 != 0:
    num_list = [int(i) for i in range(2, N, 2)]
    for num in num_list:
        if A.count(num) != 2:
            break
    else:
        if A.count(0) == 1:
            ans = (2 ** (N // 2)) % (10**7 + 7)

else:
    num_list = [int(i) for i in range(1, N, 2)]
    for num in num_list:
        if A.count(num) != 2:
            break
    else:
        ans = 2 ** (N // 2) % (10**7 + 7)

print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
if N % 2 == 0:
    if len(A) != 2*len(set(A)):
        ans = 0
else:
    if A.count(0) == 1:
        A.remove(0)
        if len(A) != 2*len(set(A)):
            ans = 0
    else:
        ans = 0
if ans == 0:
    print(0)
else:
    print((2**(N//2))%(10**9+7))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations

n,k = map(int, input().split())
pary = []
xary = []
yary = []
for _ in range(n):
    x,y = map(int, input().split())
    pary.append([x,y])
    xary.append(x)
    yary.append(y)

ret = None
for x in combinations(range(n),2):
    for y in combinations(range(n),2):
        xc = [xary[x[0]], xary[x[1]]]
        yc = [yary[y[0]], yary[y[1]]]
        cnt = 0
        for p in pary:
            if (min(xc[0],xc[1])<=p[0]<=max(xc[0],xc[1])
                and min(yc[0],yc[1])<=p[1]<=max(yc[0],yc[1])):
                cnt += 1
            if cnt==k:
                break
        if cnt>=k:
            s = abs(xc[0]-xc[1]) * (abs(yc[0]-yc[1]))
            if ret is None:
                ret = s
            else:
                ret = min(ret,s)

print(ret)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations

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

xl = []
yl = []
xy = []
for _ in range(n):
    x,y = map(int, input().split())
    xl.append(x)
    yl.append(y)
    xy.append((x,y))
yl.sort()
xy.sort(key=lambda x:x[1])

res = None
for cx in combinations(xl, 2):
    x1,x2 = cx
    if x2>x1:
        x1,x2 = x2,x1

    for y2 in yl:
        cnt = 0
        for c in xy:
            x,y = c
            if x1>=x>=x2 and y>=y2:
                cnt += 1

            if cnt==k:
                y1 = y
                s = (x1-x2)*(y1-y2)
                if res is None:
                    res = s
                else:
                    res = min(res, s)
                break

print(res)
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
dp = [1000000000] * N
dp[0] = 0

for i in range(N - 1):
  for k in range(1, K + 1):
    if i + k < N:
      dp[i + k] = min(dp[i + k], dp[i] + abs(H[i] - H[i + k]))

print(dp[-1])


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

def frog(n, k, h):
    d = [float('inf')] * n
    d[0] = 0

    for i in range(1, n):
        d[i] = min(
            d[j] + abs(h[i] - h[j]) for j in range(max(i - k, 0), i)
        )
    return d[n - 1]


print(frog(n, k, h))
### BUGGY CODE ###

N,M,C=[int(x) for x in str(input()).split()]
r=[int(x) for x in str(input()).split()]
ABC=[[0 for i in range(4)]]

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

for i in range(N):
  dis.append([100001 for i in range(N+1)])


for i in range(M):
  x=[0]+[int(x) for x in str(input()).split()]
  ABC.append(x)
  dis[x[1]][x[2]]=x[3]
  dis[x[2]][x[1]]=x[3]
  y=[0,x[2],x[1],x[3]]
  ABC.append(y)

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


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


mi=100000000000000
def perm(a,i):
  global mi
  if i==len(a):      

    p=0
    for x in range(len(a)-1):
      p+=dis[a[x]][a[x+1]]

    mi=min(mi,p)


  else:
    for j in range(i,len(a)):
      a[i],a[j]=a[j],a[i]
      perm(a,i+1)
      a[i],a[j]=a[j],a[i]


perm(r,0)

print(mi)

### FIXED CODE ###

N,M,C=[int(x) for x in str(input()).split()]
r=[int(x) for x in str(input()).split()]
ABC=[[0 for i in range(4)]]

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

for i in range(N):
  dis.append([1000000000000 for i in range(N+1)])


for i in range(M):
  x=[0]+[int(x) for x in str(input()).split()]
  ABC.append(x)
  dis[x[1]][x[2]]=x[3]
  dis[x[2]][x[1]]=x[3]
  y=[0,x[2],x[1],x[3]]
  ABC.append(y)

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


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


mi=1000000000000
def perm(a,i):
  global mi
  if i==len(a):      

    p=0
    for x in range(len(a)-1):
      p+=dis[a[x]][a[x+1]]

    mi=min(mi,p)


  else:
    for j in range(i,len(a)):
      a[i],a[j]=a[j],a[i]
      perm(a,i+1)
      a[i],a[j]=a[j],a[i]


perm(r,0)

print(mi)