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

from collections import defaultdict
S=input()
D=defaultdict(int)
D[0]=1
s=0
a=[0]*len(S)
for i in range(len(S)):
  s+=int(S[len(S)-i-1])*10**i
  a[i]=s%2019


for i in range(len(a)):
  D[a[i]]+=1

ans=sum([i*(i-1)//2 for i in D.values()])
print(ans)  

### FIXED CODE ###

from collections import defaultdict
S=input()
D=defaultdict(int)
D[0]=1
n=0
i=0
a=[0]*len(S)
b=1
for s in S[::-1]:
  n+=int(s)*b
  a[i]=n%2019
  i+=1
  b=(b*10)%2019


for i in range(len(a)):
  D[a[i]]+=1

ans=sum([i*(i-1)//2 for i in D.values()])
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
ans=[0]*N
ans[1]=abs(h[1]-h[0])
for i in range(2,N):
    cost=[]
    for j in range(1,K+1):
        if i>=j:
            c=i-j
            cost.append(abs(h[i]-h[c])+ans[c])
        else:
            break
    ans[i]=min(cost)
print(ans[-1])

### FIXED CODE ###

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

import math
x = int(input())

maxs = []
for i in range(x):
    max = 0
    for j in range(x):
        if (i+1) ** (j+2) <= x:
            max = (i+1) ** (j+2)
            maxs.append(max)
        else:
            if j == 0:
                max = (i+1) ** (j+2)
                # maxs.append(max)
    # else:
    #     maxs.append(max)


maxs.sort()
# print(maxs)
print(maxs[-1])


### FIXED CODE ###

import math
x = int(input())

maxs = []
for i in range(x):
    max = 0
    for j in range(x):
        if (i+1) ** (j+2) <= x:
            max = (i+1) ** (j+2)
            maxs.append(max)
        else:
            if j == 0:
                max = (i+1) ** (j+2)
                break
    # else:
    #     maxs.append(max)


maxs.sort()
# print(maxs)
print(maxs[-1])
### BUGGY CODE ###

# coding: utf-8
# Here your code !
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon Oct  9 22:12:40 2017

@author: kitagenbakurou
"""
import numpy as np
import copy

def insert(pos, s, x):
  return x.join([s[:pos], s[pos:] ])

s = input()
N = len(s)

i = 0
cnt = 0
flag = True
while i < N - i - 1 : 
    if s[i] != s[N - i - 1] : 
        if s[i] == "x" : 
            cnt += 1
            s = insert(N - i  , s , "x")
            i = -1
        elif s[N - i - 1] == "x" : 
            cnt += 1
            s = insert(i , s , "x")
            i = -1
        else : 
            flag = False
            break
    N = len(s)
    i += 1

if flag : 
    print(cnt)
else : 
    print(-1)

### FIXED CODE ###

# coding: utf-8
# Here your code !
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon Oct  9 22:12:40 2017

@author: kitagenbakurou
"""
import numpy as np
import copy

def insert(pos, s, x):
  return x.join([s[:pos], s[pos:] ])

s = input()
N = len(s)

i = 0
j = N - 1
cnt = 0
flag = True
while i < j : 
    if s[i] != s[j] : 
        if s[i] == "x" : 
            cnt += 1
            #s = insert(N - i  , s , "x")
            i += 1
            j += 0
        elif s[j] == "x" : 
            cnt += 1
            #s = insert(i , s , "x")
            i +=0
            j -= 1
        else : 
            flag = False
            break
    else : 
        i += 1
        j -= 1

if flag : 
    print(cnt)
else : 
    print(-1)
### BUGGY CODE ###

import itertools
cost = 10**12
N,M,X = map(int,input().split())
ca = [list(map(int,input().split())) for _ in range(N)]
combi = itertools.permutations(range(N),N)
for a in combi:
    x = [0]*M
    fx = [0]*M
    c = 0
    for i in range(len(a)):
        for j in range(1,M+1):
            x[j-1] += ca[a[i]][j]
            if x[j-1]>=X:
                fx[j-1] = 1
        c += ca[a[i]][0]
        if c>cost:
            break
        if sum(fx)==M:
            break
    if sum(fx) == M:
        cost = min(c,cost)
print(cost if cost !=10**12 else -1)

### FIXED CODE ###

import itertools
import numpy as np
 
N,M,X = map(int,input().split())
ca = ([list(map(int,input().split())) for _ in range(N)])
ca = np.array(ca)
sumX = sum(ca)[1:]
sumcos = sum(ca)[0]
cost = sumcos
if sum(sumX>=X)<M:
    print(-1)
else:
    for j in range(1,N+1):
        for a in itertools.combinations(range(1,N+1),j):       
            x = sum(ca)[1:]
            fx = np.array([0]*M)
            c = sumcos
            for i in range(len(a)):
                x -= ca[a[i]-1][1:]
                c -= ca[a[i]-1][0]
                if sum(x>=X)<M:
                    break
                else:
                    cost = min(c,cost)
    print(cost)
### BUGGY CODE ###

"""
D
"""
import sys
input=sys.stdin.readline

def match_count(lst_1,lst_2):
    l_1,l_2=len(lst_1),len(lst_2)
    kkk=0
    zzz=0
    ttt=0
    while kkk<l_1:
        while zzz<l_2:
            if lst_1[kkk]>lst_2[zzz]:
                zzz+=1
                continue
            else:
                if lst_1[kkk]==lst_2[zzz]:
                    zzz+=1
                    ttt+=1
                break
        else:
            break
        kkk+=1
    return ttt

N,M,K=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
CD=[list(map(int,input().split())) for i in range(K)]
data1=[[] for i in range(N+1)]
data2=[[] for i in range(N+1)]
for A,B in AB:
    data1[A].append(B)
    data1[B].append(A)
for C,D in CD:
    data2[C].append(D)
    data2[D].append(C)
    
for i in range(N+1):
    data1[i].sort()
    data2[i].sort()
    
    
    
ans=[0]*(N+1)
flag=[0]*(N+1)
for i in range(1,N+1):
    if flag[i]==1:
        continue
    que=[i]
    H=[i]
    flag[i]=1
    while que:
        u=que.pop()
        for v in data1[u]:
            if flag[v]==0:
                flag[v]=1
                que.append(v)
                H.append(v)
                
    H.sort()
    for u in H:
        ans[u]=len(H)-len(data1[u])-match_count(H,data2[u])-1

print(*ans[1:])



### FIXED CODE ###

#頂点xの親を求める
def find_parent(x):
    y=parent[x]
    if y<0:
        return x
    parent[x]=find_parent(y)
    return parent[x]

#頂点aと頂点bのグループをつなげる
def connect(a,b):
    c=find_parent(a)
    d=find_parent(b)
    if c==d:
        return
    if parent[c]<parent[d]:
        parent[c]+=parent[d]
        parent[d]=c
    else:
        parent[d]+=parent[c]
        parent[c]=d
    return

#N個の頂点、M本の道で、i個目の道がAi-Biとなるような
#グラフについてグループ化する
N,M,K=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
CD=[list(map(int,input().split())) for i in range(K)]
parent=[-1]*(N+1)
for A,B in AB:
    connect(A,B)
ans=[0]*(N+1)
for i in range(1,N+1):
    ans[i]=-parent[find_parent(i)]-1
for A,B in AB:
    ans[A]-=1
    ans[B]-=1
for C,D in CD:
    if find_parent(C)==find_parent(D):
        ans[C]-=1
        ans[D]-=1
print(*ans[1:])
### BUGGY CODE ###

n,m = map(int, input().split())
A = []
B = []
ans = 0
for n in range(n):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
    
while(m > 0):
    minA = min(A)
    if B[A.index(minA)] >= m:
        ans += minA*m
    else:
        ans += minA*B[A.index(minA)]
    m = m - B[A.index(minA)]
    
    B.pop(A.index(minA))
    A.pop(A.index(minA))
    
print(ans)

### FIXED CODE ###

import itertools

n,m = map(int, input().split())
AB = []
ans = 0
for n in range(n):
    a,b = map(int,input().split())
    AB.append([a,b])
AB.sort()
A,B = zip(*AB)
A,B = list(A), list(B)

i = list(_ for _ in itertools.accumulate(B) if _ <= m)
if i == []:
    ans = A[0]*m
else:
    B = B[:len(i)] + [m-i[-1]]
    A = A[:len(B)]

    ans = sum([a*b for a,b in zip(A,B)])
print(ans)
### BUGGY CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-

N = int(raw_input())
while N!=0:
    (W, H) = map(int, raw_input().split())
    PT = []
    for i in range(N):
        PT.append(map(int, raw_input().split()))
    Max = 0
    (S, T) = map(int, raw_input().split())
    for i in range(1, W+1):
        for j in range(1, H+1):
            cnt = 0
            for w in range(i, i+S):
                for t in range(j, j+T):
                    if [w, t] in PT:
                        cnt += 1
            if Max < cnt:
                Max = cnt
    print Max

    N = int(raw_input())

### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-

N = int(raw_input())
while N!=0:
    (W, H) = map(int, raw_input().split())
    E = [[0]*H for i in range(W)]
    for i in range(N):
        (x, y) = map(int, raw_input().split())
        E[x-1][y-1] = 1
    (S, T) = map(int, raw_input().split())

    Max = 0
    for i in range(W-S+1):
        for j in range(H-T+1):
            Sum = 0
            for k in range(S):
                for l in range(T):
                    Sum += E[i+k][j+l]
            if Sum > Max:
                Max = Sum
    print Max
    N = int(raw_input())
### BUGGY CODE ###

from collections import deque
N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]
G = {i:[0,[]] for i in range(N)}
for i in range(N):
    for j in range(i+1,N):
        if 0<=A[j]-A[i]<=K:
            G[i][1].append(j)
            G[j][0] += 1
            break
for i in range(N):
    for j in range(i+1,N):
        if 0<A[i]-A[j]<=K:
            G[i][1].append(j)
            G[j][0] += 1
            break
S = []
for i in range(N):
    if G[i][0]==0:
        S.append(i)
dist = [-1 for _ in range(N)]
for i in S:
    que = deque([(i,0)])
    dist[i] = 0
    while que:
        x,d = que.popleft()
        for y in G[x][1]:
            if dist[y]<d+1:
                dist[y]=d+1
                que.append((y,d+1))
dmax = max(dist)
print(dmax+1)

### FIXED CODE ###

from collections import deque
INFTY = 10**10
def update(i,a):
    j = i+N
    T[j] = a
    j = j//2
    while j>=1:
        T[j]=max(T[2*j],T[2*j+1])
        j = j//2
def find(l,r):
    que = deque([(1,0,N)])
    A = []
    while que:
        j,x,D = que.popleft()
        y = x+D
        if y<=l or x>=r:
            A.append(-INFTY)
        elif l<=x and y<=r:
            A.append(T[j])
        else:
            que.append((2*j,x,D//2))
            que.append((2*j+1,x+D//2,D//2))
    return max(A)
n,K = map(int,input().split())
A = [int(input()) for _ in range(n)]
k = 0
while 2**k<3*10**5:
    k += 1
N = 2**k
T = [-INFTY for _ in range(2*N)]
dp = [0 for _ in range(n)]
dp[0]=1
update(A[0],dp[0])
for i in range(1,n):
    a = A[i]
    l = max(0,a-K)
    r = min(a+K,N-1)+1
    dp[i] = max(1,find(l,r)+1)
    update(a,dp[i])
dmax = 0
for i in range(n):
    dmax = max(dmax,dp[i])
print(dmax)
### BUGGY CODE ###

def main():
    N,Q = map(int,input().split())
    S = input()
    lr = []
    for i in range(Q):
        lr.append(list(map(int,input().split())))

    cl = [0 for _ in range(len(S))]

    for i in range(1,len(S)):
        if S[i] == 'C' and S[i-1] == 'A':
            cl[i] = cl[i-1] + 1
        else:
            cl[i] = cl[i-1]


    #print(cl) 
    #print(S)

    for l,r in lr:
        sub = cl[l-1:r]
        res = cl[r-1] - cl[l-1] 
        print(res)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N,Q = map(int,input().split())
    S = input()
    lr = []
    for i in range(Q):
        lr.append(list(map(int,input().split())))

    cl = [0 for _ in range(len(S))]

    for i in range(1,len(S)):
        if S[i] == 'C' and S[i-1] == 'A':
            cl[i] = cl[i-1] + 1
        else:
            cl[i] = cl[i-1]


    #print(cl) 
    #print(S)

    for l,r in lr:
        res = cl[r-1] - cl[l-1] 
        print(res)


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

N = int(input())
A = list(map(int, input().split()))
digit = [0] * 60
for a in A:
    binary = bin(a)[-1:1:-1]
    for j in range(len(binary)):
        digit[j] += int(binary[j])
ans = 0
mod = 10**9+7
for i in range(60):
    ans += digit[i] * (N - digit[i]) * pow(2, i, mod)
    ans %= mod
print(ans)


### FIXED CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split()))
A = np.array(A, dtype=np.int64)
ans = 0
mod = 10**9+7
i = 1
while i < (1 << 60):
    count = np.count_nonzero(A & i)
    ans += count * (N-count) * i
    ans %= mod
    i <<= 1
print(ans)
### BUGGY CODE ###

import itertools
 
s = str(input())
 
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1

M = 1
      
for i in range(n):
  if s[n-1-i] == '?':
    for k, j in itertools.product(range(10), range(13)):
      x = (j+k*M)%13
      dp[i+1][x] += dp[i][j]
  else:
    for j in range(13):
      x = (j+int(s[n-1-i])*M)%13
      dp[i+1][x] += dp[i][j]
  M = (M*10)%13
print(dp[-1][5]%(10**9+7))
#print(dp)

### FIXED CODE ###

import itertools
 
s = str(input())
 
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1

M = 1
INF = 10 ** 9 + 7
      
for i in range(n):
  if s[n-1-i] == '?':
    for k, j in itertools.product(range(10), range(13)):
      x = (j+k*M)%13
      dp[i+1][x] += dp[i][j]
      dp[i+1][x] %= INF
  else:
    for j in range(13):
      x = (j+int(s[n-1-i])*M)%13
      dp[i+1][x] += dp[i][j]
      dp[i+1][x] %= INF
  M = (M*10)%13

print(dp[-1][5])
#print(dp[-1][5]%(10**9+7))
#print(dp)
### BUGGY CODE ###

from math import sqrt, ceil

ab = input().split(' ')
a = int(ab[0])
b = int(ab[1])

tmp = b
if a<b:
	tmp = a
	a = b
	b = tmp

while b != 0:
	tmp = b
	b = a%b
	a = tmp

count = 1
if a == 1:
	print(count)
else:
    if a%2 == 0:
        count += 1
        while a%2 == 0:
            a //= 2

    for i in range(3, a+1, 2):
        if a%i == 0:
            count += 1
            while a%i == 0:
                a //= i
            if a == 1:
                break
    print(count)

### FIXED CODE ###

from math import sqrt, ceil

def main():

    ab = input().split(' ')
    a = int(ab[0])
    b = int(ab[1])

    tmp = b
    if a<b:
        tmp = a
        a = b
        b = tmp

    while b != 0:
        tmp = b
        b = a%b
        a = tmp

    count = 1

    if a == 1:
        return count

    if a%2 == 0:
        count += 1
        while a%2 == 0:
            a //= 2
        if a == 1:
            return count
    
    i = 3
    while i*i <= a:
        if a%i == 0:
            count += 1
            while a%i == 0:
                a //= i
            if a == 1:
                return count
        i += 2
        
    return count+1

if __name__ == "__main__":
    print(main())
### BUGGY CODE ###

n=input()
s=input()

cnt=0
for i in range(0,1000):
  pos=0
  t="{0:03d}".format(i)
  for j in range(int(n)):
    if s[j] == t[pos]:
      pos+=1
    if pos == 3:
      cnt+=1
      break

print(cnt)

### FIXED CODE ###

n=input()
s=input()

cnt=0
for i in range(0,1000):
  pos=0
  t="{0:03d}".format(i)
  for j in range(int(n)):
    if s[j] == t[pos]:
      pos+=1
    if pos == 3:
      cnt+=1
      break

print(cnt)
### BUGGY CODE ###

n,k = map(int, input().split())
l = [0] + list(map(int, input().split()))
a = list()
for i in range(n):
  l[i+1] += l[i]
a = [l[j]-l[i] for i in range(n) for j in range(i+1,n+1)]
x = 0
for i in range(40,-1,-1):
  t = 2**i
  if sum(1 if y&(t+x)==t+x else 0 for y in a) >= k:
    x += t
print(x)


### FIXED CODE ###

n,k = map(int, input().split())
l = [0] + list(map(int, input().split()))
a = list()
for i in range(n):
  l[i+1] += l[i]
a = [l[j]-l[i] for i in range(n) for j in range(i+1,n+1)]
x = 0
for i in range(40,-1,-1):
  t = 2**i 
  if sum(map(lambda y:((y&(t+x)) == t+x),a)) >= k:
    x += t
print(x)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
l,r=[],[]
c=[0]*n
for i in range(q):
    a,b=map(int,input().split())
    l.append(a)
    r.append(b)
for i in range(n-1):
    if  s[i]=="A" and s[i+1]=="C":
        c[i]=1
for i in range(q):
    print(sum(c[(l[i]-1):(r[i]-1)]))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
l,r=[],[]
c=[0]*(n+1)
for i in range(q):
    a,b=map(int,input().split())
    l.append(a)
    r.append(b)
t=0
for i in range(n-1):
    if  s[i]=="A" and s[i+1]=="C":
        t+=1
    c[i+1]=t
c[n]=c[n-1]
c.append(c[n])
for i in range(q):
    print(c[r[i]-1]-c[l[i]-1])
### BUGGY CODE ###

from itertools import product


n = int(input())
lst_A = list(map(int, input().split()))
lst_B = list(map(int, input().split()))
lst_C = list(map(int, input().split()))


lst_ABC = list(product(lst_A, lst_B, lst_C))
ans = sum(1 for a, b, c in lst_ABC if a < b < c)
print(ans)

### FIXED CODE ###

import bisect


n = int(input())
lst_A = list(map(int, input().split()))
lst_B = list(map(int, input().split()))
lst_C = list(map(int, input().split()))
lst_A.sort()
lst_B.sort()
lst_C.sort()


ans = 0
for b in lst_B:
    na = bisect.bisect_left(lst_A, b)
    nc = n - bisect.bisect_right(lst_C, b)
    ans += na * nc


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

from numpy.linalg import solve

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

mountains = [[0 for i in range(N)] for j in range(N)]

for i, mount in enumerate(mountains):
    if i != N - 1:
        mount[i] = 0.5
        mount[i+1] = 0.5
    else:
        mount[0] = 0.5
        mount[i] = 0.5

print(' '.join([str(int(x)) for x in solve(mountains, dam)]))


### FIXED CODE ###

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

mountains = [0] * N

x2 = 0
for i in range(N):
    if i % 2:
        x2 -= dam[i]
    else:
        x2 += dam[i]

mountains[0] = x2 // 2
for i in range(N-1):
    mountains[i+1] = dam[i] - mountains[i]

print(' '.join([str(x*2) for x in mountains]))
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for _ in range(q):
    ans=0
    l,r=map(int,input().split())
    for i in range(l,r):
        if s[i]=='C':
            if s[i-1]=='A':
                ans+=1
    print(ans)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
a=[0]
total=0
for i in range(1,len(s)):
    if s[i]=='C':
        if s[i-1]=='A':
            total+=1
    a.append(total)
a.append(total)

for _ in range(q):
    l,r=map(int,input().split())
    print(a[r-1]-a[l-1])
### BUGGY CODE ###

from functools import reduce

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

# 評点計算

# s[0]~s[k-2]まで0埋め
s = [0 for _ in range(k-1)]

# s[n-k] = a[0] * a[1] * ... * a[n-k]
s.append(reduce(lambda x, y: x*y, [a[i] for i in range(0, n-k+1)]))

# s[i+1] = s[i] / a[i-k+1] * a[i+1]
for i in range(k-1, n-1):
    s.append(s[i] / a[i-k+1] * a[i+1])

# 出力
for i in range(k, n):
    print("Yes" if s[i] > s[i-1] else "No" )

### FIXED CODE ###

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

for i in range(k-1, n-1):
    print("Yes" if a[i+1] > a[i-k+1] else "No")
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
c = list(map(int, input().split(' ')))

sorted_a = sorted(a)
sorted_b = sorted(b)
sorted_c_r = sorted(c)[::-1]
ans = 0
for each_b in sorted_b:
    count_a = 0
    for each_a in sorted_a:
        if each_b > each_a:
            count_a += 1
        else:
            break
    count_c = 0
    for each_c in sorted_c_r:
        if each_c > each_b:
            count_c += 1
        else:
            break
    ans += count_a * count_c
print(ans)


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
c = list(map(int, input().split(' ')))

sorted_a = sorted(a)
sorted_b = sorted(b)
sorted_c = sorted(c)
ans = 0
before_a = 0
before_c = 0
count_a = 0
count_c_rest = 0
for each_b in sorted_b:
    for ai in range(before_a, len(sorted_a)):
        if each_b > sorted_a[ai]:
            count_a += 1
            before_a += 1
        else:
            before_a = ai
            break

    for ci in range(before_c, len(sorted_c)):
        if sorted_c[ci] <= each_b:
            count_c_rest += 1
            before_c += 1
        else:
            before_c = ci
            break

    ans += count_a * (len(sorted_c)-count_c_rest)
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
List = [list(map(int, input().split())) for _ in range(M)]
 
cnt = 0
for i in range(M):
    A+=[List[i][1]]*List[i][0]
    cnt+=List[i][0]
 
 
print(sum(sorted(A)[cnt:]))

### FIXED CODE ###

from heapq import heappop, heappush, heapify

N, M = map(int, input().split())
A = list(map(int, input().split()))
List = [list(map(int, input().split())) for _ in range(M)]

List = sorted(List, reverse=True, key=lambda x: x[1])

heapify(A)

i = 0
while i<M:
    m = heappop(A)
    heappush(A, m)
    tmp = List[i][1]
    cnt = List[i][0]
    while (0<cnt) and (m<tmp):
            m = heappop(A)
            heappush(A, tmp)
            tmp = List[i][1]
            cnt-=1
    i+=1

print(sum(A))
### BUGGY CODE ###

#%%
import itertools

def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d

n, m, R = map(int, input().split())
r = list(map(lambda x: int(x)-1,input().split()))
dist = [[float("inf")] * n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    dist[a][b] = c
    dist[b][a] = c
dist = warshall_floyd(dist)

l = list(itertools.permutations(r))
ans = float("inf")
for i in range(len(l)):
    tmp = 0
    for j in range(len(r)-1):
        tmp += dist[l[i][j]][l[i][j+1]]
    ans = min(ans, tmp)
print(ans)

### FIXED CODE ###

#%%
import itertools

def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d

n, m, R = map(int, input().split())
r = list(map(lambda x: int(x)-1,input().split()))
dist = [[float("inf")] * n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    dist[a][b] = c
    dist[b][a] = c
dist = warshall_floyd(dist)

l = list(itertools.permutations(r))
ans = float("inf")
for i in range(len(l)):
    tmp = 0
    for j in range(len(r)-1):
        tmp += dist[l[i][j]][l[i][j+1]]
    ans = min(ans, tmp)
print(ans)
### BUGGY CODE ###

n = int(input())
 
ans = 0
for i in range(1, n+1):
  if n in list(range(100 * i, 105 * i + 1)):
    ans = 1
print(ans)


### FIXED CODE ###

x = int(input())

flag = False
for c in range(1,x+1):
  if c * 100 <= x and x <= c * 105:
    flag = True
    break
print(1 if flag else 0)
### BUGGY CODE ###

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

for i in range(int(N)):
  print(A.count(i+1))
      

### FIXED CODE ###

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


cnt=[0]*N
for i in range(1,N):
  cnt[A[i-1]-1]=cnt[A[i-1]-1]+1

for c in cnt:
  print(c)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
C=[int(i) for i in input().split()]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
A_B=[]
SUM=[]
for i in range(min(K,X)):
  for j in range(min(K,Y)):
    A_B.append(A[i]+B[j])
A_B.sort(reverse=True)
for i in range(min(K,X*Y)):
  for j in range(min(K,Z)):
    SUM.append(A_B[i]+C[j])
SUM.sort(reverse=True)
for i in range(K):
  print(SUM[i])

### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
C=[int(i) for i in input().split()]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
SUM=[]
for i in range(X):
  for j in range(Y):
    for k in range(Z):
      if (i+1)*(j+1)*(k+1)<=K:
        SUM.append(A[i]+B[j]+C[k])
      else:
        break
SUM.sort(reverse=True)
for i in range(K):
  print(SUM[i])
### BUGGY CODE ###

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

ans = 1
for a in A:
    ans *= a
    if ans == 0:
        break

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

ans = 1
if 0 in A:
    print(0)
else:
    for a in A:
        ans *= a
        if ans > 10**18:
            ans = -1
            break

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

N, W = map(int, input().split())
dp = [0]*(W+1)
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
        dp[j] = max(dp[j], dp[j-w] + v)
print(max(dp))

### FIXED CODE ###

N, W = map(int, input().split())
dp = [0]*(W+1)
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
        dp[j] = max(dp[j], dp[j-w] + v)
print(max(dp))