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

N = int(input())
S = input()
ans = 0
lista = [[[0 for i in range(N)] for j in range(N)] for k in range(3)]
for i in range(N-2):
    a = S[i]
    for j in range(i+1,N-1):
        if a != S[j]:
            if a != 'R' and S[j] != 'R':
                lista[0][j-i][j] += 1
            elif a != 'G' and S[j] != 'G':
                lista[1][j-i][j] += 1
            elif a != 'B' and S[j] != 'B':
                lista[2][j-i][j] += 1
for k in range(2,N):
    for j in range(k):
        if S[k] == 'R':
            ans += sum(lista[0][j][:k]) - lista[0][j][k-j]
        if S[k] == 'G':
            ans += sum(lista[1][j][:k]) - lista[1][j][k-j]
        if S[k] == 'B':
            ans += sum(lista[2][j][:k]) - lista[2][j][k-j]
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
count = [[0 for i in range(N)] for j in range(3)]
for i in range(N):
    if S[i] == 'R':
        count[0][i] = 1
    if S[i] == 'G':
        count[1][i] = 1
    if S[i] == 'B':
        count[2][i] = 1
for i in range(3):
    for j in range(N-1,0,-1):
        count[i][j-1] += count[i][j]
for i in range(N-2):
    a = S[i]
    for j in range(i+1,N-1):
        b = S[j]
        if a != b:
            if a != 'R' and b != 'R':
                ans += count[0][j]
                if 2*j-i < N and S[j+j-i] == 'R':
                    ans -= 1
            if a != 'G' and b != 'G':
                ans += count[1][j]
                if 2*j-i < N and S[j+j-i] == 'G':
                    ans -= 1
            if a != 'B' and b != 'B':
                ans += count[2][j]
                if 2*j-i < N and S[j+j-i] == 'B':
                    ans -= 1
print(ans)
### BUGGY CODE ###

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

n = int(input())

power = 1

for i in range(n):
  power = power * (i+1)
  
print(power%(10**9+7))


### FIXED CODE ###

N = int(input())

power = 1
bigint = 10 ** 9 + 7
for n in range(1, N+1):
  power = power * n % bigint
print(power)
### BUGGY CODE ###

import bisect

s=input()
t=input()

index=list()
for a in range(len(t)):
 index.append([i for i, x in enumerate(s) if x == t[a]])

b=0
loop=0
condition=0

for j in range(len(t)):
  #print(j,index[j],b,c,loop)
  if len(index[j])<1:
    print(-1)
    condition=1
    break
  c=bisect.bisect_left(index[j],b)
  if j<1:
    b=index[0][0]    
  elif c == len(index[j]) or c==index[j][len(index[j])-1]: 
     loop +=1
     b=index[j][0]
  else:
     b=index[j][c]
     #print(j,b,loop)


if condition==0:
 print(b+loop*len(s)+1)


        



### FIXED CODE ###

import bisect

s=input()
t=input()

#index=list()
#for a in range(len(t)):
# index.append([i for i, x in enumerate(s) if x == t[a]])

char_appear = {ch: [] for ch in 'abcdefghijklmnopqrstuvwxyz'}
for i, ch in enumerate(s):
    char_appear[ch].append(i)
#print(char_appear['a'])
      
b=0
loop=0
condition=0

for j in range(len(t)):
  if len(char_appear[t[j]])<1:
    print(-1)
    condition=1
    break
  c=bisect.bisect(char_appear[t[j]],b)
 # print(j,char_appear[t[j]],b,c,loop)
  if j<1:
    b=char_appear[t[0]][0]    
  elif c == len(char_appear[t[j]]): #or c==char_appear[t[j]][len(char_appear[t[j]])-1]: 
     loop +=1
     b=char_appear[t[j]][0]
     if loop==10**100:
        print(-1)
        condition=1
        break
  else:
     b=char_appear[t[j]][c]
     #print(j,b,loop)


if condition==0:
 print(b+loop*len(s)+1)
### BUGGY CODE ###

N = int(input())
A = []
B = []
while len(A) != N:
    A.append(int(input()))
i = 0
while len(B) < N:
    B.append(A[0:N])
    del B[-1][i]
    print(max(B[-1]))
    i += 1

### FIXED CODE ###

N = int(input())
A = []
B = []
while len(A) != N:
    A.append(int(input()))
B = A[0:N]
B.sort()
if B[-1] == B[-2]:
    for _ in range(N):
        print(B[-1])
else:
    for _ in range(N):
        if A[_] == B[-1]:
            print(B[-2])
        else:
            print(B[-1])
### BUGGY CODE ###

n = int(input())
p = [int(i) for i in input().split()]
count = 0
for i,j in enumerate(p):
    if j == min(p[:i+1]):
        count += 1
print(count)

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]
count = 0
min_value = p[0]
for i in p:
    if i <= min_value:
        count += 1
        min_value = i
print(count)
### BUGGY CODE ###

n = int(input())
for i in range(1,n+1):
    ans = 0
    N = int((i*2)**(1/2))+1
    for j in range(1,N+1):
        for k in range(1,j+1):
            for l in range(1, k+1):
                if (j+k)**2 + (k+l)**2 + (l+j)**2 == 2*i:
                    if j==k==l:
                        ans += 1
                    elif j > k > l:
                        ans += 6
                    else:
                        ans += 3
                if (j+k)**2 + (k+l)**2 + (l+j)**2 >= 2*i:
                    break
            if (j+k)**2 > 2*i:
                break
    print(ans)

### FIXED CODE ###

from numba import njit

@njit("i8(i8)")
def loop(i):
    ans = 0
    N = int((i*2)**(1/2))+1
    for j in range(1,N+1):
        for k in range(1,j+1):
            for l in range(1, k+1):
                if (j+k)**2 + (k+l)**2 + (l+j)**2 == 2*i:
                    if j==k==l:
                        ans += 1
                    elif j > k > l:
                        ans += 6
                    else:
                        ans += 3
                if (j+k)**2 + (k+l)**2 + (l+j)**2 >= 2*i:
                    break
            if (j+k)**2 > 2*i:
                break
    return(ans)

n = int(input())
for i in range(1,n+1):
    print(loop(i))
### BUGGY CODE ###

import sys

n = int(input())
a = list(map(int, input().strip().split()))
ans = a[0]
for i in range (1,n):
 ans = ans*a[i]
if(ans > 10**18):
 print(-1)
 sys.exit()
else:
 print(ans)

### FIXED CODE ###

import sys

input = sys.stdin.readline
 
n = int(input())
a = list(map(int, input().strip().split()))
if(0 in a):
 print(0)
 sys.exit()
else:
 ans = a[0]
 for i in range (1,n):
  ans = ans*a[i]
  if(ans > 10**18):
   print(-1)
   sys.exit()
 print(ans)
### BUGGY CODE ###

k = int(input())

def test_case(k):
    ans,cnt = 7,1
    
    if k % 2 == 0 or k % 5 == 0:
        return -1
    
    if k == 1 or k == 7:
        return 1
    
    while (1):
        mod = (ans * 10 + 7) % k
        cnt += 1
        ans = ans * 10 + 7
        
        if mod == 0:
            return cnt
        
print(test_case(k))



### FIXED CODE ###

k = int(input())

def test_case(k):
    ans,cnt = 7,1
    
    if k % 2 == 0 or k % 5 == 0:
        return -1
    
    if k == 1 or k == 7:
        return 1
    
    while (1):
        ans = (ans * 10 + 7) % k
        cnt += 1
        
        if ans == 0:
            return cnt
        
print(test_case(k))
### BUGGY CODE ###

def anagram(s):
    count = 0
    for i in range(n):
        for j in range(i+1,n):
            if s[i] == s[j]:
                count += 1
    return count

n = int(input())
s = []
for i in range(n):
    li = sorted(input())
    li = ''.join(li)
    s.append(li)
print(anagram(s))

### FIXED CODE ###

def anagram(n,s):
    count = 0
    dic = {}
    for s in S:
        if s in dic:
            count += dic[s]
            dic[s] += 1
        else:
            dic[s] = 1
    return count

N = int(input())
S = []
for i in range(N):
    li = sorted(input())
    li = ''.join(li)
    S.append(li)
print(anagram(N,S))
### BUGGY CODE ###

N = int(input())
r = [int(input()) for x in range(N)]

cur_min = max(r) + 1
max_diff = min(r) - max(r) - 1
search_from_idx = 1

for i in range(N) :
    if r[i] >= cur_min :
        continue
        
    if search_from_idx <= i :
        search_from_idx = i + 1
        
    for j in range(search_from_idx, N) :
        if max_diff < r[j] - r[i] :
            max_diff = r[j] - r[i]
            search_from_idx = j

    cur_min = min(r[i], cur_min)
        
print(max_diff)


### FIXED CODE ###

n = int(input())

# initial observation
cur_min = int(input())
max_diff = -1 * (10**9) - 1

for i in range(n - 1) :
    num = int(input())
    
    max_diff = max(max_diff, num - cur_min)
    
    if num < cur_min :
        cur_min = num
    
print(max_diff)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)


N=input()
A=map(int, sys.stdin.readline().split())

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

def func(x,y,cnt):
	if dp[x][y]>0: return dp[x][y]
	ret=0
	if x==y:
		if cnt%2==0:
			ret=A[x]
			dp[x][y]=ret
			return ret
		else:
			ret=-1*A[x]
			dp[x][y]=ret
			return ret
	if cnt%2==0:
		cnt+=1
		ret=max( func(x,y-1,cnt)+A[y] , func(x+1,y,cnt)+A[x]  )
	else:
		cnt+=1
		ret=min( func(x,y-1,cnt)-A[y] ,func(x+1,y ,cnt)-A[x] )

	dp[x][y]=ret
	return ret

func(0,N-1,0)

print dp[0][N-1]


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

N=input()
A=map(int, sys.stdin.readline().split())

dp=[ [ None for i in range(N) ]  for j in range(N) ]


for i in range(N-1,-1,-1):
	if N%2==0:
		dp[i][i]=A[i]*-1
	else:
		dp[i][i]=A[i]


for i in range(N-2,-1,-1):
	for j in range(i+1,N):
		t=N-(j-i+1)	#残りの要素数
		if t%2==0:
			if dp[i][j] is None : dp[i][j]=float("-inf")
			dp[i][j]=max(dp[i][j] , dp[i][j-1]+A[j])
			dp[i][j]=max(dp[i][j] , dp[i+1][j]+A[i])
		else:
			if dp[i][j] is None : dp[i][j]=float("inf")
			dp[i][j]=min(dp[i][j] , dp[i][j-1]-A[j])
			dp[i][j]=min(dp[i][j] , dp[i+1][j]-A[i])

print dp[0][N-1]
### BUGGY CODE ###

n = int(input())
a = sorted([int(i) for i in input().split()])

def count(n,a):
    count = 0
    cmax = 0
    if n == 1:
        return 1
    else:
        for i in range(n):
            j = i
            while j <= n-1  and a[j]-a[i] <= 2:
                count += 1
                j += 1
            if count > cmax:
                cmax = count
            count = 0
        return cmax
        
print(count(n,a))

### FIXED CODE ###

from collections import Counter
n = int(input())
a = sorted([int(i) for i in input().split()])
c = Counter(a)
d =[]
for k,v in c.items():
    d.append([k,v])

    

def count(a):
    na = len(a)
    count = 0
    cmax = 0
    if n == 1:
        return 1
    else:
        for i in range(na):
            j = i
            while j <= na-1  and a[j][0]-a[i][0] <= 2:
                count += a[j][1]
                j += 1
            if count > cmax:
                cmax = count
            count = 0
        return cmax

print(count(d))
### BUGGY CODE ###

m = input()
l = list(map(int, input().split()))
ans = 1
tmp = 1000000000000000000
for i in l:
    ans *= i

if ans <= tmp:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

import sys

n = sys.stdin.readline()
l = list(map(int, sys.stdin.readline().split()))
tmp = 1000000000000000000

if 0 in l:
    print(0)
else:
    ans = 1
    for i in l:
        ans *= i
        if 1000000000000000000 < ans:
            break
    if ans <= 1000000000000000000:
        print(ans)
    else:
        print(-1)
### BUGGY CODE ###

import collections
import math

def comb(n, r):
    if n < 2:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input())
L = input().split(" ")

c = collections.Counter(L)

d = {}
tmp_total = 0 

memo1 = {}
L2 = {}

for i in c:
    if c[i] not in memo1.keys():
        tmp = comb(c[i], 2)
        memo1[c[i]] = tmp
        tmp_total += tmp
    else:
        tmp_total += memo1[c[i]]
        
total = tmp_total

for i in L:
    if c[i]-1 not in memo1.keys():
        tmp = comb(c[i]-1, 2)
        memo1[c[i]-1] = tmp
        ans = total - memo1[c[i]] + tmp
        print(ans)
    else:
        ans = total - memo1[c[i]] + memo1[c[i]-1]
        print(ans)
    

### FIXED CODE ###

import collections
import math

def comb(n, r):
    if n < 2:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input())
L = input().split(" ")

c = collections.Counter(L)

d = {}
tmp_total = 0 

memo1 = {}
L2 = {}

for i in c:
    if c[i] not in memo1.keys():
        tmp = comb(c[i], 2)
        memo1[c[i]] = tmp
        tmp_total += tmp
    else:
        tmp_total += memo1[c[i]]
        
total = tmp_total

for i in L:
    ans = total - memo1[c[i]] + memo1[c[i]]*(c[i]-2)//c[i]
    print(ans)
### BUGGY CODE ###

from itertools import accumulate

n = int(input())
s = input()
t01 = s.replace("E", "0")
t01 = t01.replace("W", "1")
t10 = str(sum((1 - int(t01[n - i - 1])) * 10 ** i for i in range(n))).zfill(n)
l1 = [int(a) for a in t01]
l2 = [int(a) for a in t10]
left = [0] + list(accumulate(l1))[:-1]
right = list(accumulate(l2[::-1]))[-2::-1] + [0]
print(min(w + e for (w, e) in zip(left, right)))

### FIXED CODE ###

from itertools import accumulate

n = int(input())
s = input()

t01 = ""
t10 = ""

for x in s:
    if x == "E":
        t01 += "0"
        t10 += "1"
    else:
        t01 += "1"
        t10 += "0"

l1 = [int(a) for a in t01]
l2 = [int(a) for a in t10]
left = [0] + list(accumulate(l1))[:-1]
right = list(accumulate(l2[::-1]))[-2::-1] + [0]
print(min(w + e for (w, e) in zip(left, right)))
### BUGGY CODE ###

import random
d = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(d)]
ans = 0
a = []
last = [0]*26
for i in range(1,d+1):
    res = -float("inf")
    index = 0
    for k in range(26):
        x = k
        tnplast = last
        tnplast[x] = i
        tnp = 0
        tnp += s[i-1][x]
        for j in range(26):
            tnp -= c[j]*(i-last[j])
        if (tnp > res):
            res = tnp
            index = k+1
    ans += res
    a.append(index)

def rec(t,x,y,ans):
    ans -= s[x-1][t[x-1]-1]
    ans += s[x-1][y-1]
    ma = d+1
    mi = 0
    for j in range(x+1,d+1):
        if (t[j-1]==t[x-1]):
            ma = j
            break
    for j in range(x-1,0,-1):
        if (t[j-1]==t[x-1]):
            mi = j
            break
    ans -= c[t[x-1]-1]*(x-mi)*(ma-x)
    ma = d+1
    mi = 0
    for j in range(x+1,d+1):
        if (t[j-1]==y):
            ma = j
            break
    for j in range(x-1,0,-1):
        if (t[j-1]==y):
            mi = j
            break
    ans += c[y-1]*(x-mi)*(ma-x)
    return ans
    
for i in range(200000):
    x = random.randrange(1,d+1)
    y = random.randrange(1,27)
    t = a
    A = rec(t,x,y,ans)
    if (ans < A):
        t[x-1] = y
        a = t
        ans = A

print(*a ,sep="\n")


### FIXED CODE ###

import random
d = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(d)]
ans = 0
last = [0]*26
for i in range(1,d+1):
    x = random.randrange(26)
    print(x+1)
### BUGGY CODE ###

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

ans = functools.reduce(operator.mul, A)
    
if ans <= 10**18:
  print(ans)
else:
  print(-1)


### FIXED CODE ###

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

def main(A):
  if 0 in A:
    print(0)
    return
  prod = 1
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return
  print(prod)
    
main(A)
### BUGGY CODE ###

import math
k = int(input())
ans = 0
for i in range (k) :
    for j in range (k) :
        for l in range (k) :
            p = math.gcd(i+1,j+1)
            if p == 1 :
                ans += 1
            else :
                ans += math.gcd(p,l+1)
print(ans)

### FIXED CODE ###

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

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

from sys import stdin
from fractions import gcd
def main():
    #入力
    readline=stdin.readline
    N=int(readline())
    A=list(map(int,readline().split()))

    mod=10**9+7
    l=1
    for i in range(N):
        l=l*A[i]//gcd(l,A[i])

    res=0
    for i in range(N):
        res+=l//A[i]
        res%=mod
    
    print(res)

if __name__=="__main__":
    main()

### FIXED CODE ###

from fractions import gcd 

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

def lcm(a,b):
   return a*b//gcd(a,b)

lcm_number=1

for i in range(N):
   lcm_number=lcm(lcm_number,A[i])

count=0
for i in range(N):
   count+=lcm_number//A[i]

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

N=int(input())
print(sum(range(1,N)))

### FIXED CODE ###

N=int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))

E=[0]*(N)
for i in range(N):
  E[i]=(P[i]+1)/2

ans=0
for i in range(N-K+1):
  val=sum(E[i:i+K])
  ans=max(ans,val)
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))

E=[0]*(N+1)
for i in range(N):
  E[i+1]=E[i]+(P[i]+1)/2

ans=0
for i in range(N-K+1):
  val=E[i+K]-E[i]
  ans=max(ans,val)
print(ans)
### BUGGY CODE ###

import sys
from itertools import product
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
h, w, k = map(int, input().rstrip().split())
CHOCO = [list(map(int, input().rstrip())) for _ in range(h)]
INF = 10**5
it = ["01"]*(h-1)
ans = INF
for x in product(*it):
    cnt = sum(map(int, x))

    agg = [[0]*(w) for _ in range(cnt+1)]
    *ls, = map(int, x+('1',))
    for i in range(w):
        prev = c = 0
        for j, split in enumerate(ls):
            if split:
                agg[c][i] = prev+CHOCO[j][i]
                prev = 0
                c += 1
            else:
                prev += CHOCO[j][i]

    tmp = [0]*(cnt+1)
    for xyz in zip(*agg):
        cannot_split = False
        can_continue = True
        for i, x in enumerate(xyz):
            if x > k:
                cannot_split = True
                break
            if x+tmp[i] > k:
                can_continue = False
                break

        if cannot_split:
            break

        if can_continue:
            for i, x in enumerate(xyz):
                tmp[i] += x
                continue
        else:
            for i, x in enumerate(xyz):
                tmp[i] = x
            cnt += 1

    if cannot_split:
        continue

    ans = min(ans, cnt)
print(ans)


### FIXED CODE ###

from itertools import product
h, w, k = map(int, input().split())
CHOCO = [list(map(int, input())) for _ in range(h)]
INF = 10**5

it = ["01"]*(h-1)
ans = INF
for x in product(*it):
    cnt = sum(map(int, x))
    agg = [[0]*(w) for _ in range(cnt+1)]
    *ls, = map(int, x+('1',))
    for i in range(w):
        prev = c = 0
        for j, split in enumerate(ls):
            if split:
                agg[c][i] = prev+CHOCO[j][i]
                prev = 0
                c += 1
            else:
                prev += CHOCO[j][i]

    tmp = [0]*(cnt+1)
    cannot_split = False

    for xyz in zip(*agg):
        cannot_split = False
        can_continue = True
        for i, x in enumerate(xyz):
            if x > k:
                cannot_split = True
                break
            if x+tmp[i] > k:
                can_continue = False
                break

        if cannot_split:
            break

        if can_continue:
            for i, x in enumerate(xyz):
                tmp[i] += x
                continue
        else:
            for i, x in enumerate(xyz):
                tmp[i] = x
            cnt += 1

    if cannot_split:
        continue

    ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

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

d = {}
for i in a:
    if not i in d.keys():
        d[i] = 1
    else:
        d[i] += 1

q = int(input())

for _ in range(q):
    b, c = map(str, input().split())
    if b in d.keys() and c in d.keys():
        d[c] += d[b]
        d.pop(b)
    elif b in d.keys():
        d[c] = d[b]
        d.pop(b)
    ans = 0
    for k, v in d.items():
        ans += int(k) * v
    print(ans)

### FIXED CODE ###

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

d = {}
t = 0
for i in a:
    if not i in d.keys():
        d[i] = 1
    else:
        d[i] += 1
    t += int(i)

q = int(input())

for _ in range(q):
    b, c = map(str, input().split())
    diff = 0
    if b in d.keys() and c in d.keys():
        diff = (int(c) - int(b)) * d[b]
        d[c] += d[b]
        d.pop(b)
    elif b in d.keys():
        diff = int(c) * d[b] - int(b) * d[b]
        d[c] = d[b]
        d.pop(b)
    t += diff
    print(t)
### BUGGY CODE ###

def gcd(a, b):
  if a%b == 0:
    return b
  else:
    return gcd(b, a%b)
def mgcd(l):
  if len(l) == 1:
    return l[0]
  else:
    new_l = []
    for i in range(-(-len(l)//2)):
      temp = gcd(l[i], l[-i-1])
      if temp == 1:
        return 1
      else:
        new_l.append(temp)
    return mgcd(new_l)

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
  a_gcd = mgcd(a[:i]+a[i+1:])
  if ans < a_gcd:
    ans = a_gcd
print(ans)

### FIXED CODE ###

def gcd(a, b):
  if a%b == 0:
    return b
  else:
    return gcd(b, a%b)
def mgcd(l):
  if len(l) == 1:
    return l[0]
  else:
    new_l = []
    for i in range(-(-len(l)//2)):
      temp = gcd(l[i], l[-i-1])
      if temp == 1:
        return 1
      else:
        new_l.append(temp)
    return mgcd(new_l)

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans1 = mgcd(a[1:])
min_gcd = 1001001001
min_idx = 0
for i in range(1,n):
  temp = gcd(a[0], a[i])
  if temp < min_gcd:
    min_gcd = temp
    min_idx = i
a.pop(min_idx)
ans2 = mgcd(a)
print(max(ans1, ans2))
### BUGGY CODE ###

a=input().split()
N=int(a[0])
W=int(a[1])
wv_list=[]
for i in range(N) :
  b=input().split()
  w=int(b[0])
  v=int(b[1])

  wv_list.append([w,v])

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


if wv_list[0][0]<=W :
    n_list[0][wv_list[0][0]]=wv_list[0][1]

for i in range(1,N) :
    for j in range(W) :
        s=j+wv_list[i][0]
        if s<=W :
            n_list[i][s]=max(n_list[i-1][j]+wv_list[i][1],n_list[i][s])

        n_list[i][j] = max(n_list[i - 1][j],n_list[i][j])

print(max(n_list[-1]))


### FIXED CODE ###

a= input().split()
N = int(a[0])
W = int(a[1])
wv_list = []
max_value = 0

#価値と重さのやつをリストにしてる
for i in range(N):
  b = input().split()
  w = int(b[0])
  v = int(b[1])
  max_value += v

  wv_list.append([w, v])

#初期化
#とりあえず、全部最大になるように
inf=float('inf')
n_list = [[inf for i in range(max_value + 1)] for j in range(N)]

#最初のアイテムに関して、重みを適切な価値のところにいれている
n_list[0][wv_list[0][1]] = wv_list[0][0]

for i in range(1, N):
  # 今まで全く選んでなかった場合に、i番目のアイテムを選んだ時
  n_list[i][wv_list[i][1]] = wv_list[i][0]
  for j in range(max_value):

    s = j + wv_list[i][1]
    #アイテムを選んだらこうなりますよってのを更新
    if s <= max_value:
      n_list[i][s] = min(n_list[i - 1][j] + wv_list[i][0], n_list[i][s])

    #選ばんかったらこうなりますよってのを更新？
    n_list[i][j] = min(n_list[i - 1][j], n_list[i][j])
  
for i in range(1, max_value):

  if n_list[-1][-i] <= W:
    print(max_value - i + 1)
    break
### BUGGY CODE ###

import itertools

inf = 10 ** 9
n, m, r = map(int, input().split())
r_list = [int(i) - 1 for i in input().split()]
a_list = [[inf for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    a_list[a][b] = a_list[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            x = a_list[i][k] + a_list[k][j]
            if x < a_list[i][j]:
                a_list[i][j] = a_list[j][i] = x
k = list(itertools.permutations(r_list))
ans = inf
for kk in k[:len(k)//2 + 1]:
    temp = 0
    for k1, k2 in zip(kk[:-1], kk[1:]):
        temp += a_list[k1][k2]
    if ans > temp:
        ans = temp
print(ans)

### FIXED CODE ###

import itertools

inf = 10 ** 9
n, m, r = map(int, input().split())
r_list = [int(i) - 1 for i in input().split()]
a_list = [[inf for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    a_list[a][b] = a_list[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(i + 1, n):
            x = a_list[i][k] + a_list[k][j]
            if x < a_list[i][j]:
                a_list[i][j] = a_list[j][i] = x
k = list(itertools.permutations(r_list))
ans = inf
for kk in k:
    temp = 0
    for k1, k2 in zip(kk[:-1], kk[1:]):
        temp += a_list[k1][k2]
    if ans > temp:
        ans = temp
print(ans)