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

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

l,r = map(int,input().split())
ans = set(range(l,r+1))

for i in range(m-1):
    tmp_l,tmp_r = map(int,input().split())
    tmp = set(range(tmp_l,tmp_r+1))
    ans = ans&tmp

print(len(ans))  

### FIXED CODE ###

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

ans_l = 0
ans_r = 100001

for i in range(m):
    tmp_l,tmp_r = map(int,input().split())
    if ans_l < tmp_l:
        ans_l = tmp_l
    if tmp_r < ans_r:
        ans_r = tmp_r
        
if ans_l <= ans_r:
    print(ans_r-ans_l+1)
else:
    print(0)
### BUGGY CODE ###

#print#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code

#別に誰も10^100なんて数が必要とはいってないのだ
def dp_resolve():
    #シミュレーションをないーーーぶにやると(|s|^2+1)//2回必要なのでTLEするよ（乱択でごまかす方法をおもいつきませんでした）
    #一番長い移動を考えると、全部Rだった場合の
    #状態を圧縮するとシミュレーションできませんか？
    #そうです、状態遷移を圧縮します　
    #いや実際はDPなんだけどさ
    S=input()
    N=len(S)
    ans=[[1]*N,[0]*N]
    
    for i in range(1<<20):#2^20回くりかえしたら10^5回より増えるやろ
        ans[(i+1)%2]=[0]*N
        for n in range(N):
            if S[n]=="R":ans[(i+1)%2][n+1]+=ans[i%2][n]
            else:ans[(i+1)%2][n-1]+=ans[i%2][n]
    
    print(*ans[0])
    return            
                     
def search_resolve():
    S=input()
    
    #Sのうち、連続する2文字が”RL”か、文末にだけ1以上がある
    #RLの効果が及ぶところごとに分割しよっかLRの真ん中で分割
    N=len(S)
    sub=[N]#kugiri
    sub2=[]#"RL"のLの位置
    for i in range(N-1):
        cont=()
        if S[i]=="L"and S[i+1]=="R":
            sub.append(i+1)
        if S[i]=="R"and S[i+1]=="L":
            sub2.append(i+1)
    sub.sort(reverse=True)
    #print(sub,sub2)

    ans=[0]*N
    temp=[0,0]
    ind=0
    for i in range(N):
        l=sub2[ind]
        temp[(l-i)%2]+=1
        if i+1 in sub:
            ans[l]+=temp[0]
            ans[l-1]+=temp[1]
            temp=[0,0]
            ind+=1
            sub.pop()
            
            
    
    print(*ans)
    
def resolve():
    dp_resolve()
    #search_resolve()
#%%submit!
resolve()

### FIXED CODE ###

#print#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code

#別に誰も10^100なんて数が必要とはいってないのだ
def resolve():
    S=input()
    #シミュレーション真面目にやると|s|^2回必要なのでTLEするよ（乱択でごまかす方法をおもいつきませんでした）
    #状態を圧縮するとシミュレーションできませんか？
    #Sのうち、連続する2文字が”RL”か、文末にだけ1以上がある
    #RLの効果が及ぶところごとに分割しよっかLRの真ん中で分割
    N=len(S)
    sub=[N]#kugiri
    sub2=[]#"RL"のLの位置
    for i in range(N-1):
        cont=()
        if S[i]=="L"and S[i+1]=="R":
            sub.append(i+1)
        if S[i]=="R"and S[i+1]=="L":
            sub2.append(i+1)
    sub.sort(reverse=True)
    #print(sub,sub2)

    ans=[0]*N
    temp=[0,0]
    ind=0
    for i in range(N):
        l=sub2[ind]
        temp[(l-i)%2]+=1
        if i+1 in sub:
            ans[l]+=temp[0]
            ans[l-1]+=temp[1]
            temp=[0,0]
            ind+=1
            sub.pop()
            
            
    
    print(*ans)
    
    
#%%submit!
resolve()
### BUGGY CODE ###

n,k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0

for i in range(n-k+1):
    if sum(p[i:i+k]) > ans:
        ans = sum(p[i:i+k])

print((ans+k)/2)


### FIXED CODE ###

n,k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0

for i in range(n-k+1):
    if i==0:
        t=sum(p[0:k])
    else:
        t=t-p[i-1]+p[i+k-1]
    ans=max(ans,t)

print((ans+k)/2)
### BUGGY CODE ###

s = input()
dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
s= '0'+s
dp[0][0] =1
mod = 1000000007
def factory (i,j):
    for premod in range(13):
        curMod = (premod*10+j)%13
        dp[i][curMod]+=dp[i-1][premod]
        dp[i][curMod]%=mod
for i in range(1,len(s)):
    if s[i]!='?':
        factory(i,int(s[i]))
    else:
        for num in range(10):
            factory(i,num)
print(dp[len(s)-1][5]%mod)

### FIXED CODE ###

s = input()
dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
s= '0'+s
dp[0][0] =1
mod = 1000000007
def factory (i,j):
    for premod in range(13):
        curMod = (premod*10+j)%13
        dp[i][curMod]+=dp[i-1][premod]
        dp[i][curMod]%=mod
for i in range(1,len(s)):
    if s[i]!='?':
        factory(i,int(s[i]))
    else:
        for num in range(10):
            factory(i,num)
print(dp[len(s)-1][5]%mod)
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
  s = input()
  s = list(s)
  s.sort()
  S.append(s)

count = 0
for i in range(len(S)-1):
  for j in range(len(S)-i-1):
    k=j+i+1
    if S[i] == S[k]:
      count += 1
print(count)

### FIXED CODE ###

#n,*sl, = map(lambda x:''.join(sorted(x)),open(0).read().split())
n = int(input())
sl = []
for i in range(n):
  S = ''.join(sorted(input()))
  sl.append(S)
count = 0
dict ={}

for s in sl:
  if s in dict:
    count += dict[s]
    dict[s] += 1
  else:
    dict[s] = 1
print(count)
### BUGGY CODE ###

def solve(i,m):
    global n
    global A
    if m == 0 :
        return True
 #   elif m < 0:
 #       return False
    elif i >= n :
        return False
    else:
        return (solve(i+1,m) or solve(i+1,m-A[i]))

global n
global A
n = int(input())
st = input()
A = list(map(int,st.split()))
#A.sort(reverse = True)
input()     # don't use the num of ans pattern. dumping!
st = input()
ans = list(map(int,st.split()))

for x in ans:
    if(solve(0,x) == True):
        print('yes')
    else:
        print('no')

### FIXED CODE ###

is_able_make = [False]*2000

input()

A = [ int( val ) for val in input().rstrip().split( ' ' ) ]
q = int(input())
M = [ int( val ) for val in input().rstrip().split( ' ' ) ]

for i in A:
    for j in range(2000-i,0,-1):
        if is_able_make[j] == True:
            is_able_make[i+j] = True
    is_able_make[i] = True

for x in M:
    if(is_able_make[x] == True):
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

def make_alphabet(now_alphabet, alphabet):
    next_alphabet = []
    for n_al in now_alphabet:
        for al in alphabet:
            next_alphabet.append(n_al+al)
    return next_alphabet

a = int(input())
b = []
for a in range(a):
    b.append(input())
alphabet = [chr(ch) for ch in range(97,123)]
now_alphabet = alphabet
count=0
flag=0

while flag==0:
    letter = []
    for word in b:
        for i in range(len(word)-count):
            letter.append(word[i:i+1+count])
    letter = list(set(letter))
    for al in now_alphabet:
        if al not in letter:
            print(al)
            flag=1
            break
    count+=1
    now_alphabet = make_alphabet(now_alphabet, alphabet)
            


### FIXED CODE ###

def make_alphabet(now_alphabet, alphabet):
    next_alphabet = []
    for n_al in now_alphabet:
        for al in alphabet:
            next_alphabet.append(n_al+al)
    return next_alphabet

a = int(input())
b = []
for a in range(a):
    b.append(input())
alphabet = [chr(ch) for ch in range(97,123)]
now_alphabet = alphabet
count=0
flag=0

while flag==0:
    letter = []
    for word in b:
        for i in range(len(word)-count):
            letter.append(word[i:i+1+count])
    rem = list(set(now_alphabet) - set(letter))
    if rem!=[]:
        print(sorted(rem)[0])
        flag=1
    count+=1
    now_alphabet = make_alphabet(now_alphabet, alphabet)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    A = inputList()
    
    ans = [0 for i in range(N)]
    ans_cnt = 0
    ans_str = ""
    for i in range(N, 0, -1):
        cons = 0
        for j in range(i, N+1, i):
            if ans[j-1] == 1:
                cons += 1
        if A[i-1] == 1 and cons % 2 == 0:
            ans[i-1] = 1
            ans_cnt += 1
            ans_str = ans_str + str(i) + " "
            continue
        if A[i-1] == 0 and cons % 2 == 1:
            ans[i-1] = 1
            ans_cnt += 1
            ans_str = ans_str + str(i) + " "
            continue
            
    print(ans_cnt)
    print(ans_str)
            	
if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
 
N=INT()
A=LIST()
 
# その位置にボールを入れるかを保持するA2
A2=[0]*N
B=[]
# 後ろから決めていく
for i in range(N-1, -1, -1):
    cur=i+1
    cnt=0
    # curの倍数を全部見に行く
    for j in range(cur*2, N+1, cur):
        cnt^=A2[j-1]
    # ボールを入れるべきかどうか
    if A[i]!=cnt:
        B.append(cur)
        A2[i]=1
 
print(len(B))
print(*B)
### BUGGY CODE ###

import sys
import bisect
from operator import itemgetter


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    _ = sys.stdin.readline()
    a = list(_ia())
    l = {}
    r = {}
    for i, ai in enumerate(a):
        li = ai + i + 1
        ri = i + 1 - ai
        l[li] = l.get(li, 0) + 1
        r[ri] = r.get(ri, 0) + 1
    ra = list(r.keys())
    ra.sort()
    n = len(ra)

    li = 0
    ans = 0
    for kl, vl in sorted(l.items(), key=itemgetter(0)):
        li += bisect.bisect_left(ra[li:], kl)
        if li >= n:
            break
        kr = ra[li]
        if kl == kr:
            ans += vl * r[kr]
    return ans


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import sys
from collections import Counter


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    _ = sys.stdin.readline()
    a = list(_ia())
    l = Counter(ai+i+1 for i, ai in enumerate(a))
    r = Counter(i+1-ai for i, ai in enumerate(a))
    return sum(v*r.get(k, 0) for k, v in l.items())


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

N, Y = map(int, input().split())
x = 0
y = 0
z = 0

if Y/1000 - N < 0:
    print(-1,-1,-1)

else:
    for i in range(0, int(Y - 1000 * N / 9000)+ 1):
        x = i
        y = (Y - 1000 * N - 9000 * x) / 4000
        if y == int(y)  and y >= 0:
            y = int(y)
            z = N - x - y
            if 0 <= z <= N:
                print(x, y, z)
                break
        if i == int(Y - 1000 * N / 9000):
            print(-1, -1, -1)
            break





### FIXED CODE ###

N, Y = map(int, input().split())
x,y,z = 0,0,0
for x in range(0, N + 1):
    for y in range(0, N - x +1):
        z = N - x - y
        if 10000 * x + 5000 * y + 1000 * z == Y:
            break
    if 10000 * x + 5000 * y + 1000 * z == Y :
        break

if 10000 * x + 5000 * y + 1000 * z == Y :
    print(x,y,z)
else:
    print(-1,-1,-1)
### BUGGY CODE ###

n = int(input())
s = input()
box = []
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if not str(s[i])+str(s[j])+str(s[k]) in box:
                box.append(str(s[i])+str(s[j])+str(s[k]))
print(len(box))

### FIXED CODE ###

n = int(input())
S = input()
count = 0
for i in range(10):
    a = S.find(str(i))
    if a == -1:
        continue
    for j in range(10):
        b = S.find(str(j),a + 1)
        if b == -1:
            continue
        for k in range(10):
            if str(k) in S[b+1::]:
                count += 1
print(count)
### BUGGY CODE ###

n = input()
for k in xrange(n):
    str1 = raw_input()
    str2 = raw_input()
    
    after = [0] * (len(str2) + 1)
    
    for i in xrange(1, len(str1) + 1):
        before = after + []
        for j in xrange(1, len(str2) + 1):
            if str1[i - 1] == str2[j - 1]:
                after[j] = before[j - 1] + 1
            elif after[j - 1] > before[j]:
                after[j] = after[j - 1]
    print after[j]

### FIXED CODE ###

def LCS():
    str1 = raw_input()
    str2 = raw_input()
    
    after = [0] * (len(str2) + 1)
    
    for i in xrange(1, len(str1) + 1):
        before = after + []
        for j in xrange(1, len(str2) + 1):
             if str1[i - 1] == str2[j - 1]:
                 after[j] = before[j - 1] + 1
             elif after[j - 1] > before[j]: #this is equal to 'max(after[j - 1], before[j])'
                 after[j] = after[j - 1]
    return after[j]

n = input()
for k in xrange(n):
    print LCS()
### BUGGY CODE ###


def main():
#    with open("input.txt", "r") as f:
#        t = f.readlines()
#        N = int(t[0].split()[0])
#        K = int(t[0].split()[1])
#        h = t[1].split()
    N, K  = map(int, input().split())
    h = list(map(int, input().split()))
#    print(h)
#    print(len(h))
    dp = [10**9] * max(N,K)
    dp[0] = 0

    for i in range(N):
#        j = 0
        L = min(K, i)
        for j in range(L+1):
            if dp[i] > dp[i-j] + abs(h[i]-h[i-j]):
                dp[i] = dp[i-j] + abs(h[i]-h[i-j])
#        while j <= L:
#            #print(i)
#            if dp[i] > dp[i-j] + abs(h[i]-h[i-j]):
#                dp[i] = dp[i-j] + abs(h[i]-h[i-j])
#            j += 1
    print(dp[N-1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K  = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**9] * N
    dp[0] = 0

    for i in range(N):
        dp[i] = min([dp[i-j] + abs(h[i]-h[i-j]) for j in range(min(K,i)+1)])
    print(dp[N-1])

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

N,K=map(int,input().split())
P=list(map(int,input().split()))
Kitai=[0]
for k in range(0,N-K+1):
  On=0
  for l in range(0,K):
    On+=(1+P[k+l])/2
  Kitai.append(On)

print(max(Kitai))

### FIXED CODE ###

#模範解答の通りにやってみる
N,K=map(int,input().split())
P=list(map(int,input().split()))
if K==1:
	print((max(P)+1)/2)
elif N==K:
	print((sum(P)+N)/2)
else:
	T=sum(P[0:(K)])
	S=sum(P[0:(K)])
	for k in range(0,N-K):
		S=S-P[k]+P[k+K]
		if T<=S:
			T=S
		else:
			continue
	print((T+K)/2)
### BUGGY CODE ###

def main():
    N = int(input())
    X = 1
    Y = 1
    Z = 1

    for n in range(1,N+1,1):
        ans = 0
        for x in range(1,101,1):
            if x**2 + Y**2 + Z**2 + x*Y + Y*Z + Z*x > n:
                break
            for y in range(1,101,1):
                if x**2 + y**2 + Z**2 + x*y + y*Z + Z*x > n:
                    break
                for z in range(1,101,1):
                    if x**2 + y**2 + z**2 + x*y + y*z + z*x == n:
                        ans += 1
                    elif x**2 + y**2 + z**2 + x*y + y*z + z*x > n:
                        break
        print(ans)



main()


### FIXED CODE ###

def main():
    N = int(input())
    X = 1
    Y = 1
    Z = 1

    a = [0]*(N+1)

    for x in range(1,101,1):
        if x**2 + Y**2 + Z**2 + x*Y + Y*Z + Z*x > N:
            break
        for y in range(1,101,1):
            if x**2 + y**2 + Z**2 + x*y + y*Z + Z*x > N:
                break
            for z in range(1,101,1):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x <= N:
                    a[x**2 + y**2 + z**2 + x*y + y*z + z*x] += 1
                elif x**2 + y**2 + z**2 + x*y + y*z + z*x > N:
                    break
    for i in range(1,N+1,1):
        print(a[i])

main()
### BUGGY CODE ###

import numpy as np


class Okojo:
    def __init__(self, line):
        self.line = line
        self.bool = np.array([], dtype=bool)
        self.get_lr()

    def get_lr(self):
        for i in range(len(self.line)):
            if self.line[i] == 'L':
                self.bool = np.append(self.bool, True)
            else:
                self.bool = np.append(self.bool, False)

    def get_l(self):
        return self.bool

    def get_r(self):
        return np.logical_not(self.bool)

    def get_next(self, state):
        l = state.copy()
        r = state.copy()
        l[self.get_r()] = 0.
        r[self.get_l()] = 0.
        l = np.roll(l, -1)
        r = np.roll(r, 1)
        return l + r


def resolve():
    line = input()

    okojo = Okojo(line)

    now = np.ones(len(line), dtype=int)
    before1 = now
    for i in range(10 ** 100):
        before2 = before1
        before1 = now
        now = okojo.get_next(before1)
        if np.all(before1 == now):
            break
        elif np.all(before2 == now):
            if i % 2 == 0:
                now = before1
            break

    li = now.tolist()
    print(*li)


resolve()

### FIXED CODE ###

def resolve():
    line = input()
    result = [0] * len(line)

    r_odd = 0
    r_even = 0
    for i in range(len(line)):
        if line[i] == 'L':
            if i % 2 == 0:
                result[i] += r_even
                result[i-1] += r_odd
            else:
                result[i] += r_odd
                result[i-1] += r_even
            r_odd = 0
            r_even = 0
        elif line[i] == 'R':
            if i % 2 == 0:
                r_even += 1
            else:
                r_odd += 1
    l_odd = 0
    l_even = 0
    for i in range(len(line)-1, -1, -1):
        if line[i] == 'R':
            if i % 2 == 0:
                result[i] += l_even
                result[i+1] += l_odd
            else:
                result[i] += l_odd
                result[i+1] += l_even
            l_odd = 0
            l_even = 0
        elif line[i] == 'L':
            if i % 2 == 0:
                l_even += 1
            else:
                l_odd += 1

    print(*result)
    
resolve()
### BUGGY CODE ###

p = int(input())
a = list(map(int, input().split()))

MOD = p
MAX = p + 10
fact = [1] * (MAX + 1)  # i!
finv = [1] * (MAX + 1)  # (i!)^{-1}
iinv = [1] * (MAX + 1)  # i^{-1}
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


b = [0] * p
for j in range(p):
    if a[j] == 1:
        b[0] += 1
        for k in range(p):
            b[k] += comb(p - 1, k) * pow(j, p - 1 - k, MOD) * (-1)**(p - k)
            b[k] %= MOD

print(*b)


### FIXED CODE ###

p = int(input())
a = list(map(int, input().split()))

MOD = p
MAX = p + 10
fact = [1] * (MAX + 1)  # i!
finv = [1] * (MAX + 1)  # (i!)^{-1}
iinv = [1] * (MAX + 1)  # i^{-1}
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


b = [0] * p
for j in range(p):
    if a[j] == 1:
        b[0] += 1
        for k in range(p):
            b[k] += comb(p - 1, k) * pow(j, p - 1 - k, MOD) * (-1)**(
                (p - k) % 2)
            b[k] %= MOD

print(*b)
### BUGGY CODE ###

import numpy as np

L, N = map(int, input().split())
X = np.array([int(input()) for _ in range(N)])
Y = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))


def func1(n):
    return np.concatenate((np.full(n + 1, N - n, dtype=np.int), np.arange(N - n - 2, -1, -2), np.arange(N - n - 1, -1, -2)[::-1]))


def func2(n):
    return np.concatenate((np.arange(N - n - 1, -1, -2), np.arange(N - n - 2, -1, -2)[::-1], np.full(n + 1, N - n, dtype=np.int)))


ans = 0
for n in range((N + 1) // 2):
    len_ = np.dot(func1(n), Y)
    ans = max(ans, len_)
    len_ = np.dot(func2(n), Y)
    ans = max(ans, len_)

print(ans)


### FIXED CODE ###

import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
X2 = L - X[::-1]
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))
Y2 = Y1[::-1]
Z = np.concatenate((np.arange(N, -1, -2), np.arange(N - 1, -1, -2)[::-1]))


def myfunc(n, x):
    return x[n + (N - n + 1)//2 - 1] - 2 * x[n - 1] - (L - x[N - (N - n + 1)//2])


len1 = np.dot(Z, Y1)
len2 = np.dot(Z, Y2)
x1 = X.tolist()
x2 = X2.tolist()
ans = max(len1, len2)
for n in range(1, (N + 1) // 2):
    len1 += myfunc(n, x1)
    len2 += myfunc(n, x2)
    ans = max(ans, len1, len2)

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

from collections import defaultdict
from itertools import product, groupby, permutations
from math import pi
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def main():
    N, M, R = map(int, input().split())
    r_list = list(map(int, input().split()))
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        dp[A][B] = C
        dp[B][A] = C

    for i in range(N):
        dp[i][i] = 0

    for m in range(N + 1):
        for s in range(N + 1):
            for e in range(N + 1):
                if dp[s][m] != INF and dp[m][e] != INF:
                    dp[s][e] = min(dp[s][e], dp[s][m] + dp[m][e])

    ans = INF
    for p in permutations(r_list, len(r_list)):
        total = 0
        for i in range(len(p) - 1):
            total += dp[p[i]][p[i + 1]]
        ans = min(ans, total)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict
from itertools import product, groupby, permutations
from math import pi
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def main():
    N, M, R = map(int, input().split())
    r_list = list(map(int, input().split()))
    dp = [[float("inf")] * (N + 1) for _ in range(N + 1)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        dp[A][B] = dp[B][A] = C

    for i in range(N):
        dp[i][i] = 0

    for m in range(N + 1):
        for s in range(N + 1):
            for e in range(N + 1):
                dist = dp[s][m] + dp[m][e]
                if dist < dp[s][e]:
                    dp[s][e] = dist

    ans = float("inf")
    for p in permutations(r_list, len(r_list)):
        total = 0
        for i in range(len(p) - 1):
            total += dp[p[i]][p[i + 1]]
            if total >= ans:
                break
        else:
            if total < ans:
                ans = total
    print(ans)

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

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

L = [float("inf") for _ in range(N+M+1)]
L[0] = 0

a = 0
b = 0
ans = 0
for k in range(len(A)):
    a += A[k]
    A[k] = a
for k in range(len(B)):
    b += B[k]
    B[k] = b

AA = [0] + A

BB = [0] + B

for k in range(N+1):
    for j in range(M+1):
        if  K >= AA[k] + BB[j]:
            ans = max(k+j, ans)
            continue
        else:
            break
print(ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a, b = [0], [0]
for i in range(N):
  a.append(a[i] + A[i])
for i in range(M):
  b.append(b[i] + B[i])
ans, j = 0, M
for i in range(N + 1):
  if a[i] > K:
    break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans, i + j)
print(ans)