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

from itertools import permutations

def conv(a):
    return int(a) - 1

N,M,R = map(int,input().split())
rseq = list(map(conv,input().split()))
graph = [[-1]*N for x in range(N)]

for i in range(M):
    A,B,C = map(int,input().split())
    A,B = A-1,B-1
    graph[A][B] = C
    graph[B][A] = C

#FloydWarshall
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][k] == -1 or graph[k][j] == -1:
                continue
            if graph[i][j] == -1 or graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

minimum = 200000000
for p in permutations(rseq):
    total = 0
    for i in range(1,R):
        total += graph[p[i]][p[i-1]]
    if total < minimum:
        minimum = total
print(minimum)


### FIXED CODE ###

from itertools import permutations
 
 
def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
                new_dist = dp[i][k] + dp[k][j]
                if dp[i][j] > new_dist:
                    dp[i][j] = new_dist
 
 
def main():
    N, M, R = [int(x) for x in input().split()]
    destinations = [int(x) for x in input().split()]
    dp = [[float('inf')]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0
    for _ in range(M):
        f, t, d = [int(x) for x in input().split()]
        dp[f][t] = dp[t][f] = d
 
    warshallFloyd(N+1, dp)
 
    minimum_cost = float('inf')
    for route in permutations(destinations, len(destinations)):
        cost = 0
        while len(route) > 1:
            f, t = route[0], route[1]
            cost += dp[f][t]
            if cost > minimum_cost:
                break
            route = route[1:]
        if cost < minimum_cost:
            minimum_cost = cost
    print(minimum_cost)
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np
MOD = 10**9 + 7
H, W = map(int, input().split())
field = [['#'] * (W + 2)]
for i in range(H):
    field.append(list('#' + input() + '#'))
field.append(['#'] * (W + 2))

dp = np.zeros((H+2, W+2),dtype=int)
dp[H][W] = 1

for i in range(H,0,-1):
    for j in range(W,0,-1):
        if field[i][j] == '#':
            continue
        else:
            dp[i][j] += dp[i][j+1] + dp[i+1][j]
        dp[i][j] %= MOD

print(dp[1][1])

### FIXED CODE ###

MOD = 10**9 + 7
H, W = map(int, input().split())
field = [['#'] * (W + 2)]
for i in range(H):
    field.append(list('#' + input() + '#'))
field.append(['#'] * (W + 2))

dp = [[0 for _ in range(W+2)] for _ in range(H+2)]
dp[H][W] = 1

for i in range(H,0,-1):
    for j in range(W,0,-1):
        if field[i][j] == '#':
            continue
        else:
            dp[i][j] += dp[i][j+1] + dp[i+1][j]
        dp[i][j] %= MOD

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

N = int(input())
S = list(input())

# print(N, S)
ans = N

for i, h in enumerate(range(N)):
    skipflg = False
    f = S[0: i]
    l = S[i]
    s = S[i+1:]
    # print(f, l, s)
    nw = 0
    ne = 0
    nw = f.count('W')
    ne = s.count('E')
    # print(nw, ne)
    # for r in f:
    #     if r != 'E':
    #         nw += 1
    #         if nw >= ans:
    #             skipflg = True
    #             break
    #         # print('not e')

    # if skipflg:
    #     break

    # for w in s:
    #     if w != 'W':
    #         ne += 1
    #         if nw+ne >= ans:
    #             skipflg = True
    #             break
    #         # print('not w')

    # if skipflg:
    #     break

    ans = min(ans, nw+ne)

print(ans)


### FIXED CODE ###

N = int(input())
S = list(input())

# print(N, S)
ans = N

f = S[0]
s = S[1:]

nw = 0
ne = 0

for w in s:
    if w != 'W':
        ne += 1

ans = nw+ne
for i in range(1, N):
    # skipflg = False
    # f = S[0: i]
    # l = S[i]
    # s = S[i+1:]
    # # print(i, f, l, s)
    # nw = f.count('W')
    # ne = s.count('E')
    # print(nw, ne)

    if S[i-1] != 'E':
        nw += 1

    if S[i] != 'W':
        ne -= 1
    # print(nw, ne)
    ans = min(ans, nw+ne)

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

n = int(input())
s = []
for i in range(n):
    s.append(int(input()))
    
p = max(s)
for i in s:
    if i != p:
        print(p)
    else:
        s.remove(p)
        print(max(s))
        s.insert(0,p)


### FIXED CODE ###

n = int(input())
s = []
p = []
for i in range(n):
    s.append(int(input()))
    
p = s[:] 
s.sort()
for i in p:
    if i != s[-1]:
        print(s[-1])
    else:
        print(s[-2])
### BUGGY CODE ###

from bisect import bisect
n=int(input())
p=list(map(int,input().split()))
data=[0]*(n+1)
for i in range(n):
    data[p[i]]=i+1
lst=[data[n]]
ans=0
if data[n-1]>data[n]:
    lst.append(data[n-1])
    a=lst[0]*(n-lst[1]+1)
    ans+=a*(n-1)
else:
    lst=[data[n-1]]+lst
    a=lst[0]*(n-lst[1]+1)
    ans+=a*(n-1)
lst.append(n+1)
lst=[0]+lst
for i in range(2,n):
    h=data[n-i]
    y=bisect(lst,h)
    L=len(lst)
    if y==1:
        a=h*(lst[2]-lst[1])
        ans+=a*(n-i)
        lst=[lst[0]]+[h]+lst[1:]
    elif y==L-1:
        a=(n-h+1)*(lst[-2]-lst[-3])
        ans+=a*(n-i)
        lst=lst[:(L-1)]+[h]+[lst[-1]]
    else:
        a=(lst[y+1]-lst[y])*(h-lst[y-1])+(lst[y]-h)*(lst[y-1]-lst[y-2])
        ans+=a*(n-i)
        lst=lst[:y]+[h]+lst[y:]
print(ans)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
f=[0]*(n+1)
for i in range(n):
    f[p[i]]=i+1
l=[0]+[i for i in range(n+1)]
r=[i+1 for i in range(n+1)]+[n+1]
ans=0
for i in range(1,n+1):
    x=f[i]
    l1,r1=l[x],r[x]
    l2,r2=l[l1],r[r1]
    ans+=i*((l1-l2)*(r1-x)+(x-l1)*(r2-r1))
    l[r1],r[l1]=l1,r1
print(ans)
### BUGGY CODE ###

from collections import deque


H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
grid = [input() for _ in range(H)]

INF = float('inf')
path = [[[(INF, INF)] * 4 for _ in range(W)] for _ in range(H)]

D = [(-1, 0), (0, 1), (1, 0), (0, -1)] # 上:0, 右:1, 下:2, 左:3

# 初期処理
q = deque()
for d in range(4):
    path[x1][y1][d] = (1, 0)  # スタート地点では(1, 0)
    q.append((x1, y1, d, 1, 0)) # (x, y, 進行方向[d], 移動回数[c], 進行済マス数[k])

# 01BFS
while q:
    x, y, d, c, k = q.popleft()

    # nx, ny: 次の座標
    # nd: 次の進行方向
    # nc: 次の移動回数
    # nk: 次の進行済マス数
    for nd in range(4):
        if nd == d:
            dx, dy = D[nd]
            nk = 1 if k == K else k + 1
            nc = c + 1 if k == K else c
        else:
            dx, dy = 0, 0
            nk = 0
            nc = c + 1
        nx = x + dx; ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny][nd] > (nc, nk):
            path[nx][ny][nd] = (nc, nk)
            if nc == c:
                q.appendleft((nx, ny, nd, nc, nk))
            else:
                q.append((nx, ny, nd, nc, nk))

# ゴール地点の最小コストを求める
ans = INF
for d in range(4):
    ans = min(ans, path[x2][y2][d][0])
ans = -1 if ans == INF else ans
print(ans)

### FIXED CODE ###

import sys
from collections import deque
h,w,k = map(int, sys.stdin.readline().rstrip("\n").split())
sx,sy,gx,gy = map(int, sys.stdin.readline().rstrip("\n").split())
sx,sy,gx,gy = sx-1,sy-1,gx-1,gy-1
labyrinth = [line.rstrip("\n") for line in sys.stdin]
INF = float('inf')
footprint = [ [[(INF,INF)]*4 for j in range(w)] for i in range(h) ]
m = [(-1, 0), (0, 1), (1, 0), (0, -1)]
q = deque()
for d in range(4):
    footprint[sx][sy][d] = (1,0)
    q.append((sx,sy,d,1,0))
while q:
    x, y, d, c, kk = q.popleft()
    for nd in range(4):
        if nd == d:
            mx,my = m[d]
            nkk = 1 if kk == k else kk + 1
            nc = c + 1 if kk == k else c
        else:
            mx,my = 0,0
            nkk = 0
            nc = c + 1
        nx = x + mx
        ny = y + my
        if 0 <= nx < h and 0 <= ny < w and labyrinth[nx][ny] == '.' and footprint[nx][ny][nd] > (nc, nkk):
            footprint[nx][ny][nd] = (nc, nkk)
            if nc == c:
                q.appendleft((nx, ny, nd, nc, nkk))
            else:
                q.append((nx, ny, nd, nc, nkk))
ans = INF
for d in range(4):
    ans = min(ans, footprint[gx][gy][d][0])
ans = -1 if ans == INF else ans
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
res = [A.count(i) for i in range(1, N + 1)]
for r in res:
    print(r)

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
for i in range(1, N + 1):
    if c[i]:
        print(c[i])
    else:
        print(0)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=list(map(int,input().split()))
    #1個がi個，2個がj個，3個がk個
    dp=[[[0.0]*(n+1) for j in range(n+1)]for i in range(n+1)]
    max_i,max_j=A.count(1),A.count(2)
    max_k=n-max_i-max_j
    for k in range(max_k+1):
        for j in range(max_j+max_k+1):
            for i in range(min(max_i+max_j+max_k+1,n-(j+k)+1)):
                if i+j+k==0:continue
                res=n
                if i>0:res+=dp[i-1][j][k]*i
                if j>0:res+=dp[i+1][j-1][k]*j
                if k>0:res+=dp[i][j+1][k-1]*k
                res/=i+j+k
                dp[i][j][k]=res
    print(dp[max_i][max_j][max_k])

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
    n=int(input())
    A=list(map(int,input().split()))
    ac=Counter(A)
    #1個がi個，2個がj個，3個がk個
    dp=[[[0.0]*(n+1) for j in range(n+1)]for i in range(n+1)]
    max_i,max_j,max_k=ac[1],ac[2],ac[3]
    for k in range(max_k+1):
        for j in range(max_j+max_k+1):
            for i in range(min(max_i+max_j+max_k+1,n-(j+k)+1)):
                if i+j+k==0:continue
                res=n
                if i>0:res+=dp[i-1][j][k]*i
                if j>0:res+=dp[i+1][j-1][k]*j
                if k>0:res+=dp[i][j+1][k-1]*k
                res/=i+j+k
                dp[i][j][k]=res
    print(dp[max_i][max_j][max_k])

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

N = int(input())
A = list(map(int,input().split()))
dup = [i for i in set(A) if A.count(i) > 1]
if not dup:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

def has_duplicates(seq):
    return len(seq) != len(set(seq))
    
N = map(int,input())
A = list(map(int,input().split()))
print("NO" if has_duplicates(A) else "YES")
### BUGGY CODE ###

N,X,Y = map(int,input().split())

ans = [0 for i in range(N+1)]

for i in range(1,N):
    checking = i

    #まずスタート地点から幅優先探索を実装
    queue = [[i,0]]

    if i >= Y:
        checked = list(range(1,i+1))
    elif i <= X:
        checked = list(range(1,i+1))
    else:
        checked = list(range(1,X))
        checked.append(i)

    while(True):
        now = queue[0]

        #ショートカット確認
        if now[0] == X:
            if Y not in checked:
                queue.append([Y,now[1]+1])
                checked.append(Y)
                if not(checking > Y):
                    ans[now[1]+1] += 1
                    # print(now[0],Y,now[1]+1)

        if now[0] == Y:
            if X not in checked:
                queue.append([X,now[1]+1])
                checked.append(X)
                if not(checking > X):
                    ans[now[1]+1] += 1
                    # print(now[0],X,now[1]+1)

        #左
        if now[0]-1 >= 1 and now[0]-1 not in checked:
            queue.append([now[0]-1,now[1]+1])
            checked.append(now[0]-1)
            if not(checking > now[0]-1):
                ans[now[1]+1] += 1
                # print(now[0],now[0]-1,now[1]+1)

        #右
        if now[0]+1 <= N and now[0]+1 not in checked:
            queue.append([now[0]+1,now[1]+1])
            checked.append(now[0]+1)
            if not(checking > now[0]+1):
                ans[now[1]+1] += 1
                # print(now[0],now[0]+1,now[1]+1)

        queue.pop(0)

        if len(checked) == N or len(queue) == 0:
            break

#回答を出力
for i in range(1,N):
    print(ans[i])


### FIXED CODE ###

N,X,Y = map(int,input().split())

ans = [0 for i in range(N+1)]

def calc_goal(start,goal):
    if goal <= X:
        return goal-start
    if goal <= Y:
        if X >= start:
            return min(goal-start,X-start+Y-goal+1)
        else:
            return min(start-X+Y-goal+1,goal-start)
    else:
        if X >= start:
            return X-start+goal-Y+1
        else:
            return min(start-X+goal-Y+1,goal-start)

for i in range(1,N):
    for j in range(i+1,N+1):
        ans[calc_goal(i,j)] += 1

for i in range(1,N):
    print(ans[i])
### BUGGY CODE ###

n,a,b=map(int,input().split())

di = 10**9+7

def pow_k(x,nt):
    if nt==0:
        return 1
    K=1
    while nt>=2:
        if nt%2!=0:
            K=(K*x)%di
        x=(x*x)%di
        nt//=2
    return (K*x)%di

ans = pow_k(2,n)-1

mi = max(a,b)

lis = [n-i for i in range(mi)]
lisr = [i+1 for i in range(mi)]


for i in range(1,mi):
    lis[i] = (lis[i-1]*lis[i])%di
    lisr[i] = pow_k(lisr[i],di-2)

for i in range(1,mi):
    lisr[i] = (lisr[i-1]*lisr[i])%di


hik =(lis[a-1]*lisr[a-1])%di
hik2 = (lis[b-1]*lisr[b-1])%di


ans = (ans - hik - hik2)%di

#print((lis[3-1]*lisr[3-1])%di)

print(ans)


### FIXED CODE ###

n,a,b=map(int,input().split())

di = 10**9+7

def pow_k(x,nt):
    if nt==0:
        return 1
    K=1
    while nt>=2:
        if nt%2!=0:
            K=(K*x)%di
        x=(x*x)%di
        nt//=2
    return (K*x)%di

ans = pow_k(2,n)-1

mi = max(a,b)

lis = [n-i for i in range(mi)]
lisr = [i+1 for i in range(mi)]


for i in range(1,mi):
    lis[i] = (lis[i-1]*lis[i])%di
    lisr[i] = pow_k(lisr[i],di-2)

for i in range(1,mi):
    lisr[i] = (lisr[i-1]*lisr[i])%di


hik =(lis[a-1]*lisr[a-1])%di
hik2 = (lis[b-1]*lisr[b-1])%di


ans = (ans - hik - hik2)%di

#print((lis[3-1]*lisr[3-1])%di)

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

n=int(input())
A=list(map(int,input().split()))
gokei=0
for i in range(1,n):
    if max(A[:i]) > A[i]:
        gokei += max(A[:i])-A[i]
    else:
        pass
print(gokei)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
gokei=0
max_=A[0]
for i in range(1,n):
    if max_ > A[i]:
        gokei += max_-A[i]
    else:
        max_=A[i]
print(gokei)
### BUGGY CODE ###

n,q = map(int,input().split())
L = [0]*n
ans = [0]*n
par = [i for i in range(n)]
for i in range(n-1):
    s,t = map(int,input().split())
    par[t-1] = s-1
for i in range(q):
    s,t = map(int,input().split())
    L[s-1] += t
for i in range(n):
    x = n-i-1
    px = x
    while px != 0:
        ans[x] += L[px]
        px = par[px]
for i in range(n):
    ans[i] += L[0]
print(' '.join(map(str,ans)))

### FIXED CODE ###

n,q = map(int,input().split())
L = [0]*(n+1)
graph = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
for i in range(q):
    a,b = map(int,input().split())
    L[a] += b
q = [(1,0)]
while len(q) > 0:
    c = q.pop()
    x, par = c[0], c[1]
    L[x] += L[par]
    for child in graph[x]:
        if par == child:
            continue
        q.append((child,x))
print(' '.join(map(str,L[1:])))
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for i in range(N // R + 1):
    for j in range(N // G + 1):
        if (N - i*R - j*G) / B >= 0 and (N - i*R - j*G) % B == 0:
            ans += 1
            
print(ans)

### FIXED CODE ###

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

def sarch(listd, num):
    if listd[len(listd) - 1] == num:
        for i in listd:
            for j in ans:
                if i == j:
                    return 0
        return 1
    return 0

N, M = map(int, input().split())
data = []
brige = []
for i in range(M):
    A, B = map(int, input().split())
    data.append([A, B])
    listdata = []
    for j in range(A, B):
        listdata.append(j)
    brige.append(listdata)


ans = []

keylist = [0 for i in range(M)]

for i in range(1, N + 1):
    for j in range(M):
        if keylist[j] != 1 and sarch(brige[j], i) == 1:
            ans.append(i)
            keylist[j] = 1
    

print(len(ans))


### FIXED CODE ###

N, M = map(int, input().split())
AB = []
for i in range(M):
    a, b = map(int, input().split())
    AB.append([b, a])
AB.sort()
for i in range(M):
    if i == 0:
       j = AB[i][0] - 1
       ans = 1
    else:
        if AB[i][1] <= j and j < AB[i][0]:
            1
        else:
            j = AB[i][0] - 1
            ans += 1

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

from collections import Counter


def main():
    N = int(input())
    s = [Counter(input()) for _ in range(N)]
    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            if s[i] == s[j]:
                ans += 1
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter


def main():
    N = int(input())
    s = ["".join(sorted(input())) for _ in range(N)]
    S = Counter(s)
    ans = 0
    for a in S.values():
        ans += sigma(a)
    print(ans)


def sigma(x):
    sum = 0
    for i in range(1, x):
        sum += i
    return sum


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

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

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 list4d(a, b, c, d, e): return [[[[e] * d for j in range(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(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
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, K = MAP()
A = LIST()

def check(omit):
    dp = list2d(N+1, K, 0)
    dp[0][0] = 1
    for i in range(1, N+1):
        for j in range(K):
            dp[i][j] |= dp[i-1][j]
            if i-1 != omit and j-A[i-1] >= 0:
                dp[i][j] |= dp[i-1][j-A[i-1]]
    
    for j in range(max(0, K-A[omit]), K):
        if dp[N][j]:
            return True
    return False

ans = 0
for i in range(N):
    if not check(i):
        ans += 1
print(ans)


### FIXED CODE ###

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

import sys
import numpy as np

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 list4d(a, b, c, d, e): return [[[[e] * d for j in range(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(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
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

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N, K = MAP()
A = LIST()

def check(omit):
    # 部分和DP
    dp = np.zeros((N+1, K), dtype=np.bool)
    dp[0,0] = 1
    for i in range(N):
        # まとめて遷移
        dp[i+1] |= dp[i]
        if i != omit and A[i] < K:
            dp[i+1,A[i]:] |= dp[i,:K-A[i]]
    # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
    for j in range(max(0, K-A[omit]), K):
        if dp[N,j]:
            return True
    # なければ不要
    return False

A.sort()
print(bisearch_min(-1, N, check))
### BUGGY CODE ###

H, W, M = map(int, input().split())
hw = []
cnt_h, cnt_w = [0] * H, [0] * W
for i in range(M):
    x, y = map(int, input().split())
    hw.append((x - 1, y - 1))
    cnt_h[x - 1] += 1
    cnt_w[y - 1] += 1

max_h, max_w = max(cnt_h), max(cnt_w)

h_list = [h for h in range(H) if cnt_h[h] == max_h]
w_list = [w for w in range(W) if cnt_w[w] == max_w]

from itertools import product

for h, w in product(h_list, w_list):
    if (h, w) not in set(hw):
        print(max_h + max_w)
        break
else:
    print(max_h + max_w - 1)
    

### FIXED CODE ###

H, W, M = map(int, input().split())
hw = set()
cnt_h, cnt_w = [0] * H, [0] * W
for i in range(M):
    x, y = map(int, input().split())
    hw.add((x - 1, y - 1))
    cnt_h[x - 1] += 1
    cnt_w[y - 1] += 1

max_h, max_w = max(cnt_h), max(cnt_w)

h_list = [h for h in range(H) if cnt_h[h] == max_h]
w_list = [w for w in range(W) if cnt_w[w] == max_w]

res = max_h + max_w - 1
for h in h_list:
    for w in w_list:
        if (h, w) not in hw:
            print(res + 1)
            exit()
print(res)
### BUGGY CODE ###

n = int(input())

for i in range(n):
    j = i + 1
    x, y, z = 1, 1, 1
    out = 0
    while x**2 + y**2 + z**2 + x*y + y*z + z*x <= j:
        while x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x <= j:
            while x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x <= j:
                out += 1 if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x == j else 0
                z += 1
            z = 1
            y += 1
        y, z = 1, 1
        x += 1
    print(out)


### FIXED CODE ###

import numpy as np
n = int(input())
A = np.zeros(n)

x, y, z = 1, 1, 1

while x**2 + y**2 + z**2 + x*y + y*z + z*x <= n:
    while x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x <= n:
        while x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x <= n:
            i = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            A[i - 1] += 1
            z += 1
        z = 1
        y += 1
    y, z = 1, 1
    x += 1
for i in range(n):
    print(int(A[i]))
### BUGGY CODE ###

import sys
n = int(sys.stdin.readline())
li = []
for _ in range(n):
  li.append(sys.stdin.readline().strip())
max = 0
li2 = list(set(li))
li3 = []
for i in li2:
  cnt = li.count(i)
  if cnt > max:
    max = cnt
    li3 = [i]
  elif cnt == max:
    li3.append(i)
li3.sort()
print('\n'.join(li3))


### FIXED CODE ###

import sys
import math
import itertools
import numpy
import collections

rl = sys.stdin.readline

n = int(rl())

li = []
for _ in range(n):
    li.append(rl().rstrip())
c = collections.Counter(li)
max_cnt = 0
li = []
for k, v in c.items():
    if v < max_cnt:
        continue
    elif v == max_cnt:
        li.append(k)
    else:
        max_cnt = v
        li = [k]
li.sort()
for i in li:
    print(i)
### BUGGY CODE ###

import itertools, operator
def combinations_with_replacement_counts(n, r):
    size = n + r - 1
    for indices in itertools.combinations(range(size), n-1):
        starts = [0] + [index+1 for index in indices]
        stops = indices + (size,)
        yield tuple(map(operator.sub, stops, starts))

a = input().split(' ')
d = int(a[0])
g = int(a[1])
p = []
c = []
for i in range(d):
	a = input().split(' ')
	p.append(int(a[0]))
	c.append(int(a[1]))

end = False

for i in range(1, 1001):
	if (g <= i*d*100 + sum(c)):
		for j in list(combinations_with_replacement_counts(d, i)):			
			score = 0
			go = True
			for l in range(len(j)):
				if j[l] > p[l]:
					go = False
					break
			if go == True:
				for l in range(len(j)):
					score += j[l] * 100 * (l + 1) + j[l]//p[l]*c[l]
				if score >= g:
					print (i)
					exit()
	

### FIXED CODE ###

d,g = map(int,input().split())
 
p = []
 
for i in range(d):
    p.append(list(map(int,input().split())))

from itertools import product
from math import ceil
 
ans = 1e09
 
for c in product([0,1],repeat=d):
    score = 0
    num = 0
    ind = 0
    for i in range(d):
        if c[i] == 1:
            score += p[i][0]*100*(i+1) + p[i][1]
            num += p[i][0]
        else:
            ind = max(i,ind)
    
    if g - score <= 0:
        ans = min(ans,num)
    elif g - score <= (p[ind][0]-1)*100*(ind+1):
        num += ceil((g-score)/(100*(ind+1)))
        ans = min(ans,num)
print(ans)