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

from collections import defaultdict,deque
import numpy as np
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

class SegmentTree:
    def __init__(self,N,d):
        self.NN = 1
        while self.NN < N:
            self.NN *= 2
        self.SegTree = [d]*(self.NN*2-1)

    def update(self,i,x): #iの値をxに更新
        i += self.NN - 1
        self.SegTree[i] = x
        while i>0:
            i = (i-1)//2
            self.SegTree[i] = self.process(self.SegTree[i*2+1],self.SegTree[i*2+2])

    def query(self,a,b,k=0,l=0,r=None): #[A,B)の値, 呼ぶときはquery(a,b)
        if r == None: r = self.NN
        if r <= a or b <= l: #完全に含まない
            return -1
        elif a <= l and r <= b : #完全に含む
            return self.SegTree[k]
        else: #交差する
            vl = self.query(a,b,k*2+1,l,(l+r)//2)
            vr = self.query(a,b,k*2+2,(l+r)//2,r)
            return(self.process(vl,vr))

    def process(self,x,y): #x,yが子の時，親に返る値
        return max(x,y)

N = inp()
hh = inpl()
aa = inpl()

seg = SegmentTree(N+1,0)

for i in range(N):
    h,a = hh[i], aa[i]
    tmp = seg.query(0,h) + a
    seg.update(h,tmp)

print(seg.query(0,N+1))


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

class SegmentTree:
    def __init__(self,N,d):
        self.NN = 1
        while self.NN < N:
            self.NN *= 2
        self.SegTree = [d]*(self.NN*2-1)

    def update(self,i,x): #iの値をxに更新
        i += self.NN - 1
        self.SegTree[i] = x
        while i>0:
            i = (i-1)//2
            self.SegTree[i] = self.process(self.SegTree[i*2+1],self.SegTree[i*2+2])

    def query(self,a,b,k=0,l=0,r=None): #[A,B)の値, 呼ぶときはquery(a,b)
        if r == None: r = self.NN
        if r <= a or b <= l: #完全に含まない
            return -1
        elif a <= l and r <= b : #完全に含む
            return self.SegTree[k]
        else: #交差する
            vl = self.query(a,b,k*2+1,l,(l+r)//2)
            vr = self.query(a,b,k*2+2,(l+r)//2,r)
            return(self.process(vl,vr))

    def process(self,x,y): #x,yが子の時，親に返る値
        return max(x,y)

N = inp()
hh = inpl()
aa = inpl()

seg = SegmentTree(N+1,0)

for i in range(N):
    h,a = hh[i], aa[i]
    tmp = seg.query(0,h) + a
    seg.update(h,tmp)

print(seg.query(0,N+1))
### BUGGY CODE ###

n = int(input())
an = list(map(int, input().split()))
m = 10**9 + 7
summary = 0
for i in range(0, n-1):
    for j in range(i+1, n):
        summary += (an[i] * an[j]) % m
        summary = summary % m
print(summary)

### FIXED CODE ###

m = 10**9 + 7
n = int(input())
an = list(map(int, input().split()))
wa = []
total = 0
for i in reversed(range(1, len(an))):
    total = total + an[i]
    wa.append(total)
wa = sorted(wa, reverse=True)
ans = 0
for i in range(0, n-1):
#     print(an[i] * wa[i])
    ans = ans + an[i] * (wa[i]%m)
    ans = ans % m
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans = 0
n = int(input())
for i in range(n):
  for j in range(n):
    for k in range(n):
      ans += gcd(i+1, j+1, k+1)
print(ans)

### FIXED CODE ###

from math import gcd
k = int(input())+1
ans = 0
for i in range(1,k):
    for j in range(1,k):
        for l in range(1,k):
            ans+=gcd(gcd(i,j),l)
print(ans)
### BUGGY CODE ###

n = int(input())
v = list(map(int, input().split()))
a = sorted(([i,v[::2].count(i)] for i in set(v[::2])), key=lambda x:x[1])
b = sorted(([j,v[1::2].count(j)] for j in set(v[1::2])),key=lambda x:x[1])
if a[-1]!=b[-1]:
    print(n-a[-1][1]-b[-1][1])
elif len(a) == 1 and len(b) == 1:
    print(min(a[-1][1],b[-1][1]))
elif len(a) ==1:
    print(n-a[-1][1]-b[-2][1])
elif len(b) ==1:
    print(n-a[-2][1]-b[-1][1])
else:
    print(min(n-a[-2][1]-b[-1][1],n-a[-1][1]-b[-2][1]))

### FIXED CODE ###

from collections import Counter
n = int(input())
v = list(map(int, input().split()))
a = Counter(v[::2]).most_common()
b = Counter(v[1::2]).most_common()
a.append([0,0])
b.append([0,0])

if a[0][0]!=b[0][0]:
    print(n-a[0][1]-b[0][1])
else:
    print(min(n-a[1][1]-b[0][1],n-a[0][1]-b[1][1]))
### BUGGY CODE ###

n, m = (int(i) for i in raw_input().split())
a = []
for i in range(m):
    a.append(int(raw_input()))

dp = [0 for i in range(n+2)]
for i in range(n+1):
    if i in a:
        dp[i] = 0
    elif i == 0:
        dp[0] = 1
    elif i == 1:
        dp[1] = 1
    else:
        dp[i] = (dp[i-1] + dp[i-2])

print (dp[n] % 1000000007)


### FIXED CODE ###

n, m = (int(i) for i in raw_input().split())
a = set([])
for i in range(m):
    a.add(int(raw_input()))

dp = [0 for i in range(n+2)]
for i in range(n+1):
    if i in a:
        dp[i] = 0
    elif i == 0:
        dp[0] = 1
    elif i == 1:
        dp[1] = 1
    else:
        dp[i] = (dp[i-1] + dp[i-2])

print (dp[n] % 1000000007)
### BUGGY CODE ###

n = int(input())
s = [input() for _ in range(n)]

import numpy as np
s = np.array(s)
tt = [[],[]]
for i in s:
    if i not in tt[0]:
        tt[0] += [i]
        tt[1] += [1]
    else:
        idx = tt[0].index(i)
        tt[1][idx] += 1
tt = np.array(tt)

tidx = np.argsort(tt[0])
t = tt[:, tidx]
m = max(t[1])
ans = []
for i in range(len(t[1])):
    if t[1][i] == m:
        ans += [t[0][i]]

for i in range(len(ans)): print(ans[i])

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
s.sort()

a = ""
tt = [[],[]]
for i in s:
    if a != i:
        a = i
        tt[0] += [i]
        tt[1] += [1]
    else:
        tt[1][-1] += 1
t = tt
m = max(t[1])
ans = []
for i in range(len(t[1])):
    if t[1][i] == m:
        ans += [t[0][i]]

for i in range(len(ans)): print(ans[i])
### BUGGY CODE ###

n=input()
a=list(map(str,input().split()))
result=""
i=0
while i<len(a):
  if len(a)%2!=0:
    if i%2==0:
      result=a[i]+","+result
    else:
      result=result+","+a[i]
  else:
    if i%2==0:
      result=result+","+a[i]
    else:
      result=a[i]+","+result
  #print(result)
  i=i+1

print(*result.replace(",,",",").split(","))

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b=a[::-2]+a[N%2::2]
print(*b)
### BUGGY CODE ###

N = int(input())
S = []
for n in range(N):
    S.append(input())


def main():
    while True:
        unique = list(set(S))
        #print(unique)

        if len(unique) == len(S):
            return S

        for u in unique:
            S.remove(u)

        #print(S)


out = main()
out = sorted(out)
for o in out:
    print(o)


### FIXED CODE ###

import collections

N = int(input())
S = []
for n in range(N):
    S.append(input())

c = collections.Counter(S)
most_common = c.most_common()
#print(most_common)

max_count = most_common[0][1]

# for t in most_common:
#     print(t[1])
c_list = [t[0] for t in most_common if t[1] == max_count]
# print(sorted(c_list))

out = sorted(c_list)
for o in out:
    print(o)
### BUGGY CODE ###

n = int(input())
ss = input()

ab = "abcdefghijklmnopqrstuvwxyz"
xx = [ab.index(s) for s in ss]

#print(xx)
cnt = 0
max_cnt = 0
i = 0
while i < n:
    j = i + 1
    while j < n:
        if xx[i] == xx[j]:
            while j + cnt < n and i + cnt < j:
                if xx[i + cnt] == xx[j + cnt]:
                    cnt += 1
                else:
                    break
            max_cnt = max(max_cnt, cnt)
            #print(xx[i:(i + cnt)], xx[j:(j + cnt)], i, j, cnt)
            cnt = 0
            j = j + cnt + 1

        else:
            j += 1
            if j >= n - 1:  
                break
    #print(i, j, cnt)
    i += 1
print(max_cnt)

### FIXED CODE ###

n = int(input())
ss = input()

max_cnt = 0
for i in range(1, n):
    cnt = 0
    for j in range(n - i):
        if ss[j] == ss[j + i]:
            cnt += 1
            max_cnt = max(cnt, max_cnt)
            if cnt == i:
                break
        else:
            cnt = 0

print(max_cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    ans = 0
    for i in range(2 ** N):
        weight = 0
        value = 0
        for j in range(N):
            if (i >> j) & 1:
                weight += shina[j][0]
                value += shina[j][1]
                if weight > W:
                    value = 0
                    break

        ans = max(ans, value)

    print(ans)

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N - 1, -1, -1):
        for j in range(W + 1):
            if shina[i][0] > j:
                dp[j][i] = dp[j][i + 1]
            else:
                dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


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

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
rage=range #lol
for i in rage(1,n):
    dp[i]=10**9;
    for j in range(1,k+1):
        if i-j<0:
            break;
        dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[-1])


### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
rage=range #lol
for i in rage(1,n):
    dp[i]=10**9;
    for j in range(1,k+1):
        if i-j<0:
            break;
        dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[-1])
### BUGGY CODE ###

N, Q = [int(v) for v in input().split()]

va = [N-1] * (N - 1)
ha = [N-1] * (N - 1)

count = 0
black = (N - 2) * (N - 2)
vmax = N - 1
hmax = N - 1
for i in range(Q):
    a, b = [int(v)-1 for v in input().split()]
    if a == 0:
        i = ha[b]
        if vmax > b:
            vmax = b
            va[1:i] = [b] * (i - 1)
        count += i - 1
    else:
        i = va[b]
        if hmax > b:
            hmax = b
            ha[1:i] = [b] * (i - 1)
        count += i - 1

print(black - count)


### FIXED CODE ###

def main():
    N, Q = [int(v) for v in input().split()]

    Query = [[int(v)-1 for v in input().split()] for _ in range(Q)]

    rows = [N-1] * (N - 1)
    cols = [N-1] * (N - 1)

    black = (N - 2) * (N - 2)
    min_row = N - 1
    min_col = N - 1

    for ty, x in Query:
        if ty == 0:
            if x < min_col:
                for j in range(x, min_col):
                    rows[j] = min_row
                min_col = x
            black -= rows[x] - 1
        else:
            if x < min_row:
                for j in range(x, min_row):
                    cols[j] = min_col
                min_row = x
            black -= cols[x] - 1

    print(black)

main()
### BUGGY CODE ###

d=[i:=0]*8**7
for j in[*open(0)][1].split():d[int(j)]+=1
while i<1e6:
 i+=1;j=i
 while j<1e6:j+=i;d[j]*=d[i]<1
print(d.count(1))

### FIXED CODE ###

d = [0] * (10**6 + 1)
n = int(input())
for a in map(int, input().split()):
    d[a] += 1
ans = 0
for i in range(1, 10**6 + 1):
    if d[i] == 1:
        ans += 1
    if d[i] > 0:
        for j in range(i, 10**6 + 1, i):
            d[j] = 0
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

class Node():
    def __init__(self, key, prev=None, nex=None):
        self.key = key
        self.prev = prev
        self.next = nex
    
class DoublyLinkedLiset():
    def __init__(self):
        self.nil = Node(None)
        self.nil.next = self.nil
        self.nil.prev = self.nil
    
    def insert(self, x):
        X = Node(x)
        X.next = self.nil.next
        self.nil.next.prev = X
        self.nil.next = X
        X.prev = self.nil

    def listSearch(self, x):
        cur = self.nil.next
        while (cur != self.nil and cur.key != key):
            cur = cur.next
        
        return cur

    def deleteNode(self, X):
        if X == self.nil:
            return
        X.prev.next = X.next
        X.next.prev = X.prev
        del X

    def deleteFirst(self):
        self.deleteNode(self.nil.next)

    def deleteLast(self):
        self.deleteNode(self.nil.prev)

    def deleteKey(self, x):
        self.deleteNode(self.listSearch(x))

    def printList(self):
        cur = self.nil.next
        isf = 0
        while cur != self.nil:
            if isf > 0:
                print(" ", end="")
            print(cur.key, end="")
            cur = cur.next
            isf += 1
        print()

if __name__ == '__main__':

    n = int(input())
    dll = DoublyLinkedLiset()

    for i in range(n):
        line = input().split(" ")
        if len(line) == 2:
            command, key = line
            if command == "insert":
                dll.insert(key)
            elif command == "delete":
                dll.deleteKey(key)

        else:
            command = line[0]
            if command == "deleteFirst":
                dll.deleteFirst()
            elif command == "deleteLast":
                dll.deleteLast()

    dll.printList()
    



### FIXED CODE ###

# -*- coding: utf-8 -*-

from collections import deque

if __name__ == '__main__':
    n = int(input())
    L = deque()

    for _ in range(n):
        command = input().split(" ")
        if command[0] == "insert":
            L.appendleft(command[1])
        elif command[0] == "delete":
            try:
                L.remove(command[1])
            except:
                pass
        elif command[0] == "deleteFirst":
            L.popleft()
        elif command[0] == "deleteLast":
            L.pop()

    print(" ".join(L))
### BUGGY CODE ###

import itertools


def main():
    input()
    t = input()
    dic = {'R': [], 'G': [], 'B': []}
    for i in range(len(t)):
        dic[t[i]].append(i)
    count = 0
    p = itertools.product(dic['R'], dic['G'], dic['B'])
    for i in p:
        tmp = sorted(list(i))
        if tmp[1] - tmp[0] != tmp[2] - tmp[1]:
            count += 1

    print(count)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main3():
    n = int(input())
    s = input()

    ans = s.count("R") * s.count("B") * s.count("G")
    for i in range(n):
        for j in range(i, n):
            k = 2 * j - i
            if k >= n: break
            if s[i] != s[j] and s[j] != s[k] and s[i] != s[k]:
                ans -= 1

    print(ans)

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

def main():
    h,w=map(int,input().split())
    a=[list(map(int,input().split())) for _ in [0]*h]
    b=[list(map(int,input().split())) for _ in [0]*h]
    c=[[abs(a[i][j]-b[i][j]) for j in range(w)] for i in range(h)]
    t=4000
    dp1=[[False]*(t+1) for _ in [0]*w]
    dp1[0][c[0][0]]=True
    for j in range(1,w):
        v=c[0][j]
        for k in range(t+1):
            if dp1[j-1][k]==True:
                if v+k<=t:
                    dp1[j][v+k]=True
                if abs(v-k)<=0:
                    dp1[j][abs(v-k)]=True
    for i in range(1,h):
        dp2=[[False]*(t+1) for _ in [0]*w]
        for j in range(w):
            v=c[i][j]
            for k in range(t+1):
                if dp1[j][k]==True:
                    if v+k<=t:
                        dp2[j][v+k]=True
                    if abs(v-k)<=t:
                        dp2[j][abs(v-k)]=True
        for j in range(1,w):
            v=c[i][j]
            for k in range(t+1):
                if dp2[j-1][k]==True:
                    if v+k<=t:
                        dp2[j][v+k]=True
                    if abs(v-k)<=t:
                        dp2[j][abs(v-k)]=True  
        dp1=dp2
    for i,j in enumerate(dp1[w-1]):
        if j==True:
            print(i)
            break
main()


### FIXED CODE ###

def main():
    h,w=map(int,input().split())
    a=[list(map(int,input().split())) for _ in [0]*h]
    b=[list(map(int,input().split())) for _ in [0]*h]
    c=[[abs(a[i][j]-b[i][j]) for j in range(w)] for i in range(h)]
    t=7160
    dp1=[[False]*(t+1) for _ in [0]*w]
    dp1[0][c[0][0]]=True
    for j in range(1,w):
        v=c[0][j]
        for k in range(t+1):
            if dp1[j-1][k]==True:
                if v+k<=t:
                    dp1[j][v+k]=True
                if abs(v-k)<=0:
                    dp1[j][abs(v-k)]=True
    for i in range(1,h):
        dp2=[[False]*(t+1) for _ in [0]*w]
        for j in range(w):
            v=c[i][j]
            for k in range(t+1):
                if dp1[j][k]==True:
                    if v+k<=t:
                        dp2[j][v+k]=True
                    if abs(v-k)<=t:
                        dp2[j][abs(v-k)]=True
        for j in range(1,w):
            v=c[i][j]
            for k in range(t+1):
                if dp2[j-1][k]==True:
                    if v+k<=t:
                        dp2[j][v+k]=True
                    if abs(v-k)<=t:
                        dp2[j][abs(v-k)]=True  
        dp1=dp2
    for i,j in enumerate(dp1[w-1]):
        if j==True:
            print(i)
            break
main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
A = [int(a) for a in input().split()][::-1]
for _ in range(Q):
    x = int(input())
    l, r = 0, (N+1)//2
    while r - l > 1:
        m = (l+r) // 2
        if A[m] + A[2*m] >= 2 * x:
            l = m
        else:
            r = m
    l += 1
    print(sum(A[:l] + A[2*l::2]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
def calc(x):
    l, r = 0, (N+1)//2
    while r - l > 1:
        m = (l+r) // 2
        if A[m] + A[2*m] >= 2 * x:
            l = m
        else:
            r = m
    return l
    
N, Q = map(int, input().split())
A = [int(a) for a in input().split()][::-1]
B = [A[0]] + [0] * (N-1)
for i in range(1, N):
    B[i] = B[i-1] + A[i]
C = [A[0]] + [0] * (N-1)
for i in range(2, N, 2):
    C[i] = C[i-2] + A[i]
C[-1] += C[-2]
for _ in range(Q):
    x = int(input())
    c = calc(x)
    print(B[c] + (C[-1] - C[2*c] if c*2<=N else 0))
### BUGGY CODE ###

# coding: utf-8
# Your code here!

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

count = N
Sum = 0

for l in range(0, N-1):
    Sum = A[l]
    for r in range(l+1, N):
        #print(l,r)
        if Sum + A[r] != Sum ^ A[r]:
            break
        else:
            Sum += A[r]
            count += 1
    #count += r-l
    #if r== l:
    #    r += 1
    #else:
    #    Sum -= A[l]
print(count)

### FIXED CODE ###

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

count = 0
Sum = 0
r = 0

for l in range(0, N):
    #Sum = A[l]
    while r < N and Sum + A[r] == Sum ^ A[r]:
            Sum += A[r]
            r += 1
    count += r-l
    if(l==r):
        r+=1
    else:
        Sum -= A[l]
    
    
print(count)
### BUGGY CODE ###

r=range(1,int(input())+1)
import math
from functools import reduce
def g(*n):return reduce(math.gcd, n)
print(sum(g(a,b,c) for a in r for b in r for c in r))

### FIXED CODE ###

r=range(1,int(input())+1)
from math import gcd 
print(sum(gcd(gcd(a,b),c) for a in r for b in r for c in r))
### BUGGY CODE ###


import numpy as np

N, W=[int(i) for i in input().split()]
wv=[[int(i) for i in input().split()] for _ in range(N)]

dp=np.zeros((N,W+1)).astype("int64")


for i in range(N):
    for w in range(W+1):
        if i==0:
            if wv[i][0]<=w:
                dp[i][w]=wv[i][1]
        else:
            if w>=wv[i][0]:
                dp[i][w]=max(dp[i-1][w-wv[i][0]]+wv[i][1],dp[i-1][w])
            else:
                dp[i][w]=dp[i-1][w]

print(int(dp[-1].max())) 

### FIXED CODE ###



N, W=[int(i) for i in input().split()]
wv=[[int(i) for i in input().split()] for _ in range(N)]


dp=[[0]*(W+1) for _ in range(N)]

for i in range(N):
    for w in range(W+1):
        if i==0:
            if wv[i][0]<=w:
                dp[i][w]=wv[i][1]
        else:
            if w>=wv[i][0]:
                dp[i][w]=max(dp[i-1][w-wv[i][0]]+wv[i][1],dp[i-1][w])
            else:
                dp[i][w]=dp[i-1][w]

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

import sys
sys.setrecursionlimit(10 ** 6)

n,m,k = map(int,input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.append(1)
b.append(1)
ans = 0

def dfs(time,count,i,j):
    global ans,n,m,k,a,b
    if i <= n-1 and time + a[i] <= k:
            dfs(time + a[i],count + 1,i+1,j)
    if j <= m-1 and time + b[j] <= k:
           dfs(time + b[j],count + 1,i,j+1)  
    if (i == n or time + a[i] > k) and (j == m or time + b[j] > k):
        ans = max(ans, count)

shoki_time = 0
shoki_count = 0
shoki_i = 0
shoki_j = 0
dfs(shoki_time,shoki_count,shoki_i,shoki_j)
print(ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
acum1=[0]
for i in range(n): #累積和ai,bjを求める
 acum1.append(acum1[-1]+arr1[i])
acum2=[0]
for i in range(m):
 acum2.append(acum2[-1]+arr2[i])
ans=0
j=m
for i in range(n+1):
 if acum1[i]>k: #ai>Kであれば、どのようにjを選んでもai+bj<=Kとなることはないので探索を終了する
   break
 while acum2[j]>k-acum1[i] and j>0: #各iについて、bj<=K-aiを満たす最大のjを求める
   j-=1
 ans=max(ans,i+j)
print(ans)
### BUGGY CODE ###

import itertools
N, M, R = map(int, input().split())
rs = list(itertools.permutations(list(map(lambda x: int(x) - 1, input().split()))))
dist = [[10**9 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    v1, v2, d = map(int, input().split())
    dist[v1-1][v2-1] = dist[v2-1][v1-1] = d
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ans = 10**9
for r in rs:
    t = 0
    for i in range(R-1):
        t += dist[r[i]][r[i+1]]
    ans = min(t, ans)
print(ans)

### FIXED CODE ###

from itertools import permutations
N, M, R = map(int, input().split())
rs = map(lambda x: int(x) - 1, input().split())
dist = [[10**9 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    v1, v2, d = map(int, input().split())
    dist[v1-1][v2-1] = dist[v2-1][v1-1] = d
for i in range(N):
    dist[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ans = 10**9
for r in permutations(rs):
    t = 0
    for i in range(R-1):
        t += dist[r[i]][r[i+1]]
        if t > 10**9:
            break
    ans = min(t, ans)
print(ans)
### BUGGY CODE ###

n=int(input())
arr=list(map(int,input().split()))
c=1
arr.sort()
d=0
for i in arr:
    c=c*i
    if(c>10**18):
        d=1
        print(-1)
if(d==0):
    print(c)

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
c=1
arr.sort()
d=0
for i in arr:
    c=c*i
    if(c>10**18):
        d=1
        print(-1)
        break
if(d==0):
    print(c)
### BUGGY CODE ###

def cmb(a,b,c):
    b = min(b,a-b)
    num = 1
    for i in range(b):
        num = num*(a-i) % c
    den = 1
    for i in range(b):
        den = den*(i+1) % c
    return num * pow(den,c-2,c) % c
mod = 10**9+7
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
ans = 0
for i in range(n-k+1):
    ans -= a[i] * cmb(n-i-1,k-1,mod)
    ans %= mod
for i in range(n-k+1):
    ans += a[-i-1] * cmb(n-i-1,k-1,mod) 
    ans %= mod
print(ans)

### FIXED CODE ###

def cmb(a,b,c):
    b = min(b,a-b)
    num = 1
    for i in range(b):
        num = num*(a-i) % c
    den = 1
    for i in range(b):
        den = den*(i+1) % c
    return num * pow(den,c-2,c) % c
mod = 10**9 + 7
n,k = map(int,input().split())
inv = [0,1]
for i in range(2,n):
  inv += [inv[mod % i]*(mod - mod//i) % mod]
a = list(map(int,input().split()))
a.sort()
ans = 0
c = 1
x = 1
if k == 1:
    print(0)
    exit()
for i in range(n-k+1):
    ans -= a[n-k-i] * c
    ans += a[k+i-n-1] * c
    ans %= mod
    c = c*(i+k)*inv[i+1] % mod
if ans < 0:
    ans += mod
print(ans)