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

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()

dp = [[] for i in range(n)]
ans = 0

for i in range(n):
    b = i+a[i]
    if b < n:
        for j in range(b,n):
            if a[j] == j-b:
                ans += 1

print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()

from collections import defaultdict
d = defaultdict(int)
ans = 0

for i in range(n):
    ans += d[i-a[i]]
    d[a[i]+i] += 1

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

def abc144_e():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))
    A.sort()
    F.sort(reverse=True)

    low = -1
    up = 10**12
    while up - low > 1:
        v = (up + low) // 2
        tk = K
        for i in range(N):
            tk -= max(0, A[i] - (v // F[i]))
            if tk < 0: break
        if tk < 0:
            low = v
        else:
            up = v
    print(up)

if __name__ == '__main__':
    abc144_e()

### FIXED CODE ###

def abc144_e():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))
    A.sort()
    F.sort(reverse=True)

    low = -1
    up = 10**12
    while up - low > 1:
        v = (up + low) // 2
        tk = K
        for i in range(N):
            tk -= max(0, A[i] - (v // F[i]))
            if tk < 0: break
        if tk < 0:
            low = v
        else:
            up = v
    print(up)

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

import collections

N = int(input())
data = [input() for i in range(N)]

dicdata = collections.Counter(data)

newdata = [k for k, v in dicdata.items() if v == max(dicdata.values())]

newdata.sort()

[print(i) for i in newdata]


### FIXED CODE ###

import collections

N = int(input())
data = [input() for i in range(N)]

dicdata = collections.Counter(data)

m = max(dicdata.values())

newdata = [k for k, v in dicdata.items() if v == m]

newdata.sort()

[print(i) for i in newdata]
### BUGGY CODE ###

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

# a.sort(reverse=True)
for i in range(m):
    a[a.index(max(a))] /= 2

ans = 0
for i in range(n):
    ans += a[i] // 1

print(int(ans))


### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = list(map(lambda x: x*(-1), a))

heapq.heapify(a)
for i in range(m):
  heapq.heappush(a, heapq.heappop(a) / 2)

ans = 0
for i in range(n):
  ans += -a[i] // 1

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

import sys

def main():
    INF = 2**60
    N, M = map(int, sys.stdin.readline().split())
    XYZ = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

    sgn = [[1,1,1], [1,1,-1],[1,-1,1],[1,-1,-1],[-1,1,1],[-1,1,-1],[-1,-1,1],[-1,-1,-1]]
    ans = -INF 
    for a, b, c in sgn:
        dp = [-INF]*(M+1)
        dp[0] = 0
        for x, y, z in XYZ:
            for j in range(M-1, -1, -1):
                if dp[j] == -INF: continue
                s = dp[j]+ a*x + b*y + c*z
                if s > dp[j+1]:
                    dp[j+1] = s
        if dp[M] > ans:
            ans = dp[M]
    print(ans)

main()


### FIXED CODE ###

import sys

def main():
    INF = -2**60
    N, M = map(int, sys.stdin.buffer.readline().split())
    XYZ = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

    sgn = [[1,1,1], [1,1,-1],[1,-1,1],[1,-1,-1],[-1,1,1],[-1,1,-1],[-1,-1,1],[-1,-1,-1]]
    ans = INF 
    for a, b, c in sgn:
        dp = [INF]*(M+1)
        dp[0] = 0
        for x, y, z in XYZ:
            for j in range(M-1, -1, -1):
                if dp[j] == INF: continue
                s = dp[j]+ a*x + b*y + c*z
                if s > dp[j+1]:
                    dp[j+1] = s
        if dp[M] > ans:
            ans = dp[M]
    print(ans)

main()
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
A.sort()
table = [True for i in range(N)]
for i in range(N):
    if table[i]:
        if i < N-1 and A[i] == A[i+1]:
            table[i] = False
        for j in range(i+1, N):
            if A[j] % A[i] == 0:
                table[j] = False
print(table.count(True))


### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
A.sort()
a_max = max(A)
table = [True for i in range(a_max+1)]
for a in A:
    i = 2
    k = a * 2
    while k <= a_max:
        table[k] = False
        k += a
count = 0
for i, a in enumerate(A):
    if i < N - 1 and A[i] == A[i+1]:
        table[a] = False
    if table[a]:
        count += 1
print(count)
### BUGGY CODE ###

N = int(input())

p = 2
counter = 0
while N != 1:
  ind = 0
  n = -1
  while N % p == 0:
    N //= p
    ind += 1
  while (n+1)*(n+2)//2 <= ind:
    n += 1
  counter += n
  p += 1

print(counter)


### FIXED CODE ###

import math

N = int(input())

p = 2
counter = 0
while N != 1:
 if p > math.sqrt(N):
  counter += 1
  break
 ind = 0
 n = -1
 while N % p == 0:
  N //= p
  ind += 1
 if ind == 0:
  p += 1
  continue
 while (n+1)*(n+2)//2 <= ind:
  n += 1
 counter += n
 p += 1

print(counter)
### BUGGY CODE ###

n=int(input())

cnt=0
for i in range(1,n+1):
  for j in range(1,n+1):
    if i*j>=n:
      break
    else:
      cnt+=1
      
print(cnt)

### FIXED CODE ###

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

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

import numpy as np
N = int(input())

sushi = np.bincount(np.array(input().split(), dtype=np.int8),minlength=4)
total = (sushi * np.arange(4)).sum()

# a,b,c = 1個、2個、3個
# S = a + 2b + 3c：total スシ
# S の小さい方から求めていく
# S ごとには、b,c だけ持てば a が分かる

b = np.arange(N+1)[:,None]
c = np.arange(N+1)[None,:]
S_bc = 2 * b + 3 * c
dp = np.zeros((N+1,N+1))
for S in range(1,total+1):
    prev = dp
    a = S - S_bc
    dp = np.ones_like(prev) * N
    dp += prev * a# 1個の皿
    dp[1:] += prev[:-1] * b[1:] # 2個の皿
    dp[:-1,1:] += prev[1:,:-1] * c[:,1:] # 3個の皿
    dp /= (a+b+c)
    dp[a < 0] = 0

answer = dp[sushi[2],sushi[3]]
print(answer)

### FIXED CODE ###

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

import numpy as np
N = int(input())

sushi = np.bincount(np.array(input().split(), dtype=np.int8),minlength=4)
total = (sushi * np.arange(4)).sum()

# a,b,c = 1個、2個、3個
# S = a + 2b + 3c：total スシ
# S の小さい方から求めていく
# S ごとには、b,c だけ持てば a が分かる

b = np.arange(N+1)[:,None]
c = np.arange(N+1)[None,:]
S_bc = 2 * b + 3 * c
dp = np.zeros((N+1,N+1))
for S in range(1,total+1):
    prev = dp
    a = S - S_bc
    dp = prev * a + N
    dp[1:] += prev[:-1] * b[1:]
    dp[:-1,1:] += prev[1:,:-1] * c[:,1:]
    dp /= (a+b+c)
    dp[a < 0] = 0

answer = dp[sushi[2],sushi[3]]
print(answer)
### BUGGY CODE ###

n=int(input())
a=[list(input()) for i in range(n)]
count=0
for i in range(len(a)):
    for j in range(i+1,len(a)):
        lst = a[i].copy()
        for element in a[j]:
            try:
                lst.remove(element)
            except ValueError:
                pass
        if len(lst)==0:
            count+=1
print(count)

### FIXED CODE ###

import math
import collections

n=int(input())
a=[list(input()) for i in range(n)]
b=[str(sorted(list(i))) for i in a]
count=list(collections.Counter(b).values())
count=[i for i in count if i>1]
print(int(sum([math.factorial(x)/(math.factorial(x-2)*2) for x in count])))
### BUGGY CODE ###

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

answer = 0
for i in range(len(A)-1):
  for j in range(len(A)-i-1):
    answer += A[i] * A[j+ i + 1]
mod_answer = answer % (10**9 + 7)


print(mod_answer)

### FIXED CODE ###

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

answer = 0
x = 0
for i in range(len(A) - 1):
  x += A[i]
  answer +=  (x * A[i + 1])

print(answer% (10**9 + 7))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
n = int(input())
s = str(n)

INF = float('inf')
dp0 = [INF for _ in range(len(s)+1)]
dp1 = [INF for _ in range(len(s)+1)]
dp0[0]=0
dp1[0]=1
for i in range(len(s)):
    dp0[i+1] = min(dp0[i]+int(s[i]), dp1[i]+10-int(s[i]), dp1[i]+int(s[i])+1)
    dp1[i+1] = min(dp0[i]+int(s[i])+1,dp1[i]+10-int(s[i])-1)

print(dp0[-1])

### FIXED CODE ###

s = input()
l = len(s)

INF = float('inf')
dp = [[INF]*2 for _ in range(l+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(l):
    num = int(s[i])
    dp0 = dp[i][0]
    dp1 = dp[i][1]
    dp[i+1][0] = min(dp0+num, dp1+min(10-num,num+1))
    dp[i+1][1] = min(dp0+num+1,dp1+10-num-1)

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

R,G,B,N = map(int,input().split())
count = 0
for i in range(3001):
	for j in range (3001):
		if i*R+j*G<=N:
			tmp = N-(i*R+j*G)
			if tmp % B == 0:
				count += 1
print(count)


### FIXED CODE ###

R,G,B,N = map(int,input().split())
count = 0
for i in range(3001):
	for j in range (3001):
		if i*R+j*G<=N:
			tmp = N-(i*R+j*G)
			if tmp % B == 0:
				count += 1
print(count)
### BUGGY CODE ###

def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista 

def japonska_gierka(): 
    N = wczytaj_liste()[0]
    A = wczytaj_liste()
    X = 0
    Y = 0
    wynik = {}
    for dlugosc_kolejki in range(N+1):
        zabrano = N - dlugosc_kolejki
        for lewo in range(zabrano+1): 
            prawo = zabrano - lewo
            if dlugosc_kolejki == 0: 
                wynik[lewo,prawo] = 0 
            else:
                wynik[lewo,prawo] = max(A[lewo]-wynik[lewo+1, prawo], A[-prawo-1]-wynik[lewo,prawo+1])
    print(wynik[0,0])
    
japonska_gierka()

### FIXED CODE ###

def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista 

def japonska_gierka(): 
    N = wczytaj_liste()[0]
    A = wczytaj_liste()
    X = 0
    Y = 0
    wynik = [[None for i in range(N+1)] for j in range(N+1)]
    for dlugosc_kolejki in range(N+1):
        zabrano = N - dlugosc_kolejki
        for lewo in range(zabrano+1): 
            prawo = zabrano - lewo
            if dlugosc_kolejki == 0: 
                wynik[lewo][prawo] = 0 
            else:
                wynik[lewo][prawo] = max(A[lewo]-wynik[lewo+1][prawo], A[-prawo-1]-wynik[lewo][prawo+1])
    print(wynik[0][0])
    
japonska_gierka()
### BUGGY CODE ###

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

ans = 0
R = 0

while 1:
     G = 0
     if R*r>n:
          break
     while 1:
          if R*r+G*g>n:
               break
          if (n-R*r-G*g)%b == 0:
               ans += 1
          G += 1
     R += 1
     
print(ans)

### FIXED CODE ###

r,g,b,n = map(int,input().split())
f = [r,g,b]
f.sort()
r,g,b = f[2],f[1],f[0]

ans = 0
R = 0

while 1:
     G = 0
     if R*r>n:
          break
     while 1:
          if R*r+G*g>n:
               break
          if (n-R*r-G*g)%b == 0:
               ans += 1
          G += 1
     R += 1
     
print(ans)
### BUGGY CODE ###

from sys import setrecursionlimit

setrecursionlimit(10000)

N = int(raw_input())
health = map(int, raw_input().strip().split())

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def gcd_driver(lst):
	if len(lst) <= 1:
		return lst[0]

	if len(lst) > 2:
		lst[1] = gcd(lst[0], lst[1])
		return gcd_driver(lst[1:])

	return gcd(lst[0], lst[1])

print(gcd_driver(health))

### FIXED CODE ###

N = int(raw_input())
health = map(int, raw_input().strip().split())

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

if len(health) == 1:
	print health[0]
else:
	g = gcd(health[0], health[1])
	for i in range(2, len(health)):
		g = gcd(g, health[i])
print g
### BUGGY CODE ###

mod=10**9+7
s=input()
n=len(s)
Sum_A=[0]*(n+1)
Sum_B=[0]*(n+1)
Sum_C=[0]*(n+1)
Sum_q=[0]*(n+1)
for i in range(1, n+1):
    Sum_A[i]=Sum_A[i-1]
    Sum_C[i]=Sum_C[i-1]
    Sum_q[i]=Sum_q[i-1]
    if s[i-1]=='A':
        Sum_A[i]+=1
    elif s[i-1]=='C':
        Sum_C[i]+=1
    elif s[i-1]=='?':
        Sum_q[i]+=1
ans=0
def count(x, q):
    return int(x*3**q+q*3**(q-1))
for i in range(n):
    if s[i]=='B' or s[i]=='?':
        ans+=count(Sum_A[i], Sum_q[i])*count(Sum_C[n]-Sum_C[i+1], Sum_q[n]-Sum_q[i+1])
        ans%=mod
print(ans)

### FIXED CODE ###

mod=10**9+7
s=input()
n=len(s)
Sum_A=[0]*(n+1)
Sum_B=[0]*(n+1)
Sum_C=[0]*(n+1)
Sum_q=[0]*(n+1)
for i in range(1, n+1):
    Sum_A[i]=Sum_A[i-1]
    Sum_C[i]=Sum_C[i-1]
    Sum_q[i]=Sum_q[i-1]
    if s[i-1]=='A':
        Sum_A[i]+=1
    elif s[i-1]=='C':
        Sum_C[i]+=1
    elif s[i-1]=='?':
        Sum_q[i]+=1
ans=0
def count(x, q):
    return int(x*pow(3, q, mod)+q*pow(3, (q-1), mod)) if q>0 else int(x*pow(3, q, mod))
for i in range(n):
    if s[i]=='B' or s[i]=='?':
        ans+=count(Sum_A[i], Sum_q[i])*count(Sum_C[n]-Sum_C[i+1], Sum_q[n]-Sum_q[i+1])
        ans%=mod
print(ans)
### BUGGY CODE ###

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

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort(key=lambda x: x[1])

kid = deque(ki)
ver = []
check = []
for i in range(N):
    ver.append(0)
    check.append(False)
 
for c in co:
    ver[c[0]-1] += c[1]

check[0] = True

while len(kid) != 0:
    k = kid.popleft()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid.append(k)


print(' '.join(map(str,ver)))


### FIXED CODE ###

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

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort(key=lambda x: x[1])

kid = deque(ki)
ver = []
check = []
for i in range(N):
    ver.append(0)
    check.append(False)
 
for c in co:
    ver[c[0]-1] += c[1]

check[0] = True

kid2 = deque()

while len(kid) != 0:
    k = kid.popleft()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.append(k)

while len(kid2) != 0:
    k = kid2.pop()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.appendleft(k)


print(' '.join(map(str,ver)))
### BUGGY CODE ###

def binary_search(l, item):

    if len(l) == 0 or l[0] <= item:
        return -1

    if item < l[-1]:
        return len(l) - 1

    list2 = [1001] + l + [0]

    low = 0
    high = len(list2) - 1

    while low <= high:
        mid = (low + high) // 2

        bigger = list2[mid]
        smaller = list2[mid+1]

        if smaller <= item and item < bigger:

            return mid - 1

        if smaller > item:
            low = mid + 1

        else:
            high = mid - 1

    return -1

N = int(input())
L = list(map(int, input().split(' ')))

L = sorted(L, reverse=True)


result = 0
for i, a in enumerate(L):
    for j, b in enumerate(L[i+1::]):
        k = binary_search(L[i+j+2::], a-b)
        if k == -1:
            break
        result += k + 1


print(result)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(lambda l: int(l)*(-1), input().split()))
L.sort()

result = 0
for i, a in enumerate(L[:-2:]):
    for ii, b in enumerate(L[i+1:-1:]):
        c_list = L[i+ii+2::]
        c_index = bisect_left(c_list, a-b)
        result += c_index

print(result)
### BUGGY CODE ###

import re
S = input()
ans = 0

while True:
    num0 = S.count('01')
    S = re.sub('01', '', S)
    num1 = S.count('10')
    S = re.sub('10', '', S)
    ans += 2*(num0+num1)
    if num0+num1 == 0:
        print(ans)
        break
    


### FIXED CODE ###

import re
S = input()
print(2*min(S.count('0'), S.count('1')))
### BUGGY CODE ###

N, M = list(map(int, input().split()))
L = [None] * M
R = [None] * M
for i in range(M):
    L[i], R[i] = list(map(int, input().split()))

l = [0] * N
for i in range(M):
    for j in range(L[i], R[i] + 1):
        l[j - 1] += 1
a = 0
for i in range(N):
    if l[i] == M:
        a += 1
print(a)

### FIXED CODE ###

N, M = list(map(int, input().split()))
L = [None] * M
R = [None] * M
for i in range(M):
    L[i], R[i] = list(map(int, input().split()))

l = [L[0], R[0]] 
for i in range(1, M):
    if L[i] > l[0]:
        l[0] = L[i]
    if R[i] < l[1]:
        l[1] = R[i]

if l[0] <= l[1]:
    ans = l[1] - l[0] + 1
else:
    ans = 0
print(ans)
### BUGGY CODE ###

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

ans=0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if s==x+y+z:
                ans+=1
print(ans)

### FIXED CODE ###

k,s=map(int, input().split())
ans=0
for x in range(k+1):
    for y in range(k+1):
        if 0<=(s-x-y)<=k:
            ans+=1
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
re_flag = False 
start = ""
finish = ""
for i in range(Q):
    l = input()
    if l == "1":
        re_flag = not bool(re_flag)
    elif len(l) > 1:
        t, f, c = l.split()
        if f == "1":
            if re_flag:
                finish = finish + c
            else:
                start = c + start
        else:
            if re_flag:
                start = c + start
            else:
                finish = finish + c


S = start + S + finish
if re_flag:
    S = S[::-1]
print(S)




### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())
re_flag = False 
start = deque()
finish = deque()
for i in range(Q):
    l = input()
    if l == "1":
        re_flag = not bool(re_flag)
    else:
        t, f, c = l.split()
        if f == "1":
            if re_flag:
                finish.append(c)
            else:
                start.append(c)
        else:
            if re_flag:
                start.append(c)
            else:
                finish.append(c)

S.extend(finish)
S.extendleft(start)

ans = deque()
if re_flag:
    ans.extendleft(S)
else:
    ans = S

print("".join(list(ans)))
### BUGGY CODE ###

#D
n = int(input())
s = input()
s_l = list(s)
a = [0 for _ in range(n)]
for i in range(n):
    if s[i] =='R':
        a[i] = 0
    elif s[i] == 'G':
        a[i] = 1
    else:
        a[i] = 2
        

cnt = 0
for i in range(n-2):
    for j in range(i,n-1):
        if a[i] != a[j]:
            for k in range(j,n):
                if a[i] != a[k] and a[j] != a[k] and j-i != k-j:
                    cnt += 1

print(cnt)
     

### FIXED CODE ###

#D
n = int(input())
s = input()
s_l = list(s)

a = s_l.count('R') * s_l.count('G') * s_l.count('B')
cnt = 0
#i,j,kがそれぞれ異なり、j-i = k-jであるものを求める
for i in range(n-2):
    for j in range(i,n-1):
        if 2*j - i < n:
            if s_l[i] != s_l[j] and s_l[i] != s_l[2*j-i] and s_l[j] != s_l[2*j-i]:
                cnt += 1
                
print(a - cnt)
### BUGGY CODE ###

import copy

class warshallFloyd:
    def __init__(self, adj):
        # math.infはpython3.5以降のみ使用可能
        self.inf = 10 ** 9
        self.dis = copy.deepcopy(adj)
        for i in range(len(adj)):
            for j in range(len(adj)):
                if i != j and adj[i][j] == 0:
                    self.dis[i][j] = self.inf

    # 全ての頂点間の最短距離を算出、
    def search(self):
        for k in range(len(self.dis)):
            for i in range(len(self.dis)):
                for j in range(len(self.dis)):
                    if self.dis[i][j] > self.dis[i][k] + self.dis[k][j]:
                        self.dis[i][j] = self.dis[i][k] + self.dis[k][j]
        return self.dis


def func(n, m, r, adj):
    war = warshallFloyd(adj)
    dis = war.search()

    def depth(visited, prev, last):
        if last == 0:
            # print("visited:{} prev:{}, last:{}".format(
                # visited, r[prev], last))
            return 0
        add = war.inf
        for i in range(len(visited)):
            if not visited[i]:
                _visited = copy.deepcopy(visited)
                _visited[i] = True
                add = min(add, dis[r[prev]][r[i]] + depth(_visited, i, last - 1))
                # print("add:{}".format(add))
        return add

    _min = war.inf
    for i in range(len(r)):
        # iをスタートとする
        visited = [False for _ in range(len(r))]
        visited[i] = True
        _min = min(_min, depth(visited, i, len(r) - 1))
    return str(_min)

n, m, R = [int(i) for i in input().split()]
r = [int(i) - 1 for i in input().split()]
adj = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in input().split()]
    adj[a - 1][b - 1] = c
    adj[b - 1][a - 1] = c
print(func(n, m, r, adj))
"""
print("2 vs "+func(3, 3, [0, 1, 2], [[0, 1, 4], [1, 0, 1], [4, 1, 0]]))
print("4 vs "+func(3, 3, [0, 2], [[0, 2, 6], [2, 0, 2], [6, 2, 0]]))
print("3 vs "+func(4, 6, [1, 2, 3], [[0, 4, 6, 1], [4, 0, 3, 2], [6, 3, 0, 1], [1, 2, 1, 0]]))
# print("print(func({}, {}, {}, {}))".format(n, m, r, adj))
"""


### FIXED CODE ###

import itertools
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
dis = [[float("inf") for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    dis[a - 1][b - 1] = c
    dis[b - 1][a - 1] = c

def war(dis):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dis[i][j] > dis[i][k] + dis[k][j]:
                    dis[i][j] = dis[i][k] + dis[k][j]
    return dis
dis = war(dis)
_min = float("inf")
it = itertools.permutations(r)
for iterR in it:
    _dis = 0
    start = iterR[0] - 1
    for end in iterR[1:]:
        _dis += dis[start][end - 1]
        start = end - 1
    _min = min(_min, _dis)
print(_min)
### BUGGY CODE ###

first_input = list(map(int, input().split()))
number = first_input[0]
steps = first_input[1]

scaffolds = list(map(int, input().split()))

start_cost = scaffolds[0]

costs = []

for i in range(number):
    next_step = i
    next_scaffold = scaffolds[next_step]
    target_cost = -1
    for j in range(steps):
        
        last_step = next_step - (j + 1)
        if -1 < last_step:
            cost = abs(scaffolds[next_step] - scaffolds[last_step]) + costs[last_step]
            if target_cost == -1 or cost < target_cost:
                target_cost = cost

    if 0 < target_cost:
        next_cost = target_cost
    else:
        next_cost = scaffolds[next_step]

    
    costs.append(next_cost)

print(costs[number - 1] - start_cost)

### FIXED CODE ###

first_input = list(map(int, input().split()))
number = first_input[0]
steps = first_input[1]

scaffolds = list(map(int, input().split()))

start_cost = scaffolds[0]

costs = []

for i in range(number):
    next_step = i
    next_scaffold = scaffolds[next_step]
    target_cost = -1
    for j in range(steps):
        
        last_step = next_step - (j + 1)
        if -1 < last_step:
            cost = abs(scaffolds[next_step] - scaffolds[last_step]) + costs[last_step]
            if target_cost == -1 or cost < target_cost:
                target_cost = cost

    if 0 < target_cost:
        next_cost = target_cost
    else:
        next_cost = scaffolds[next_step]

    
    costs.append(next_cost)

print(costs[number - 1] - start_cost)