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

import numpy as np


def read():
    N = int(input().strip())  # N <= 10**5
    edges = dict()
    for i in range(N-1):
        # u[i] < v[i] は保証されている
        u, v, w = list(map(int, input().strip().split()))
        if u - 1 in edges.keys():
            edges[u - 1].update({v - 1: w % 2})
        else:
            edges.update({u - 1: {v - 1: w % 2}})
        if v - 1 in edges.keys():
            edges[v - 1].update({u - 1: w % 2})
        else:
            edges.update({v - 1: {u - 1: w % 2}})
    return N, edges


def solve(N, edges):
    c = np.ones((N, ), dtype=np.uint8) * -1  # -1: unvisited, 0: white, 1: black
    stack = list()
    c[0] = 0
    stack.append(0)
    while len(stack) > 0:
        s = stack.pop()
        for t in edges[s].keys():
            if c[t] == -1:
                if edges[s][t]:
                    c[t] = 1 - c[s]
                else:
                    c[t] = c[s]
                stack.append(t)
    return c


if __name__ == '__main__':
    inputs = read()
    colors = solve(*inputs)
    for col in colors:
        print("%d" % col)


### FIXED CODE ###

import numpy as np


def read():
    N = int(input().strip())  # N <= 10**5
    to = [[] for _ in range(N)]
    cost = [[] for _ in range(N)]
    for i in range(N-1):
        # u[i] < v[i] は保証されている
        u, v, w = list(map(int, input().strip().split()))
        to[u-1].append(v-1)
        to[v-1].append(u-1)
        cost[u-1].append(w % 2)
        cost[v-1].append(w % 2)
    return N, to, cost


def solve(N, to, cost):
    c = [-1] * N  # -1: unvisited, 0: white, 1: black
    q = list()
    c[0] = 0
    q.append(0)
    while len(q) > 0:
        s = q.pop()
        for t, co in zip(to[s], cost[s]):
            if c[t] == -1:
                if co:
                    c[t] = 1 - c[s]
                else:
                    c[t] = c[s]
                q.append(t)
    return c


if __name__ == '__main__':
    inputs = read()
    colors = solve(*inputs)
    for col in colors:
        print("%d" % col)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().split()))

def solve():
    n = I()
    edge = [[] for _ in range(n)]
    for v in range(1,n):
        u = I()-1
        edge[u].append(v)

    dp = [None]*n
    def dfs(s)->int:
        if dp[s] != None:
            return dp[s]
        if len(edge[s]) == 0:
            dp[s] = 0
            return 0
        tmp = []
        for v in edge[s]:
            tmp.append(dfs(v))
        tmp.sort(reverse=True)
        m = 0
        for i,j in enumerate(tmp):
            m = max(m,(i+1)+j)
        dp[s] = m
        return m
    dfs(0)
    print(dp[0])

if __name__=='__main__':
    solve()



### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [None]*n
def dfs(s):
    if dp[s] != None:
        return dp[s]
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    tmp.sort(reverse=True)
    m = 0
    for i,j in enumerate(tmp):
        m = max(m,(i+1)+j)
    dp[s] = m
    return m

dfs(0)
print(dp[0])
### BUGGY CODE ###

n =int(input())
ls = []
for i,j in enumerate(input().split()):
    if n%2==0:
        if i%2==0:
            ls.append(j)
        else:
            ls.insert(0,j)
    else:
        if i%2==1:
            ls.append(j)
        else:
            ls.insert(0,j)
print(" ".join(ls))

### FIXED CODE ###

n =int(input())
a = list(map(str,input().split()))
lss = []
lse = []
if n%2==0:
    for i in range(n//2):
        lss.append(a[2*i])
    for i in range(n//2):
        lse.append(a[n-(2*i+1)])

else:
    for i in range(n//2):
        lss.append(a[2*i+1])
    for i in range(n//2+1):
        lse.append(a[n-2*i-1])


ls = lse+lss

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

s = input()
l = len(s)
f = 0
for i in range(1 << l + 1):
    ans = ""
    for j in range(l + 1):
        if i >> j & 1: ans += 'A'
        if j < l: ans += s[j]
    if ans == "AKIHABARA":
        f = 1
if f: print("YES")
else: print("NO")

### FIXED CODE ###

s = input()
l = len(s)
f = 0
if l <= 9:
    for i in range(1 << l + 1):
        ans = ""
        for j in range(l + 1):
            if i >> j & 1: ans += 'A'
            if j < l: ans += s[j]
        if ans == "AKIHABARA":
            f = 1
else: f = 0

if f: print("YES")
else: print("NO")
### BUGGY CODE ###

HWD=input()
HWD=HWD.rstrip().split(" ")
H=int(HWD[0])
W=int(HWD[1])
D=int(HWD[2])

list1=[[0,0]]*(H*W)
for i in range(H):
    line=input()
    line=line.rstrip().split(" ")
    for j in range(W):
        list1[int(line[j])-1]=[i,j]
#print(list1)


    
N=int(input())
#print(N)

for k in range(N):
    LR=input()
    LR=LR.rstrip().split(" ")
    L=int(LR[0])
    R=int(LR[1])
    
    if L==R:
        print(0)
    else:
        count=0
        for l in range(int((R-L)/D)):
            L1=list1[L-1]
            L2=list1[L+D-1]
            #print(L1)
            #print(L2)
            count=count+((L1[0]-L2[0])**2)**0.5+((L1[1]-L2[1])**2)**0.5
            L=L+D
        print(int(count))
    

### FIXED CODE ###

H,W,D=map(int,input().split())
L=[0 for i in range(H*W+1)]
A=[]
for i in range(H):
    a=list(map(int,input().split()))
    A.append(a)
    
for i in range(H):
    for j in range(W):
        L[A[i][j]]=[i+1,j+1]
L[0]=[0,0]
#print(L)
l=[0 for i in range(H*W+1)]
for i in range(D):
    for j in range(H*W+1):
        if (i+j*D)>(H*W):
            break
        elif j==0:
            l[i+j*D]=0
        else:
            l[i+j*D]=l[i+(j-1)*D]+abs(L[i+j*D][0]-L[i+(j-1)*D][0])+abs(L[i+j*D][1]-L[i+(j-1)*D][1])
#print(l)
Q=int(input())
for i in range(Q):
    a,b=map(int,input().split())
    print(l[b]-l[a])
### BUGGY CODE ###

def reversed_num(num):
    num_len=len(bin(num))-2
    f= 2**num_len-1
    return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
    x= reversed_num(number.pop(-1))+1
    if x in number:
        number.remove(x)
        count+=1
print(count)

### FIXED CODE ###

import bisect
def reversed_num(num):
  num_len=len(bin(num))-2
  f=2**num_len-1
  return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
  k=number.pop()
  if len(number)==0:
    break
  if k==int(k):
    x=reversed_num(k)+1
    y=bisect.bisect_left(number,x)
    if x>number[-1]:
      y-=1
    if number[y] ==x:
      number[y]-=0.5
      count+=1
print(count)
### BUGGY CODE ###

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

A = [0] * n
B = [0] * n
for i in range(n):
    A[i], B[i] = map(int, input().split())

dp = [float("inf")] * (h+1)
dp[0] = 0

for i in range(h):
    for j in range(n):
        next_index = min(i + A[j], h)
        dp[next_index] = min(dp[next_index], dp[i] + B[j])

print(dp[-1])


### FIXED CODE ###

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

A = [0] * n
B = [0] * n
for i in range(n):
    A[i], B[i] = map(int, input().split())

dp = [float("inf")] * (h+1)
dp[0] = 0

for i in range(h):
    for j in range(n):
        next_index = min(i + A[j], h)
        dp[next_index] = min(dp[next_index], dp[i] + B[j])

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

import sys
input=sys.stdin.readline
n=int(input())
L=list(int(input()) for i in range(n))
for i in range(n):
    N=sorted(L)
    print(N[-1] if L[i]!=N[-1] else N[-2])

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
n=int(input())
L=list(int(input()) for i in range(n))
N=sorted(L)
for i in range(n):
    print(N[-1] if L[i]!=N[-1] else N[-2])
### BUGGY CODE ###

#ABC127D-IntegerCards.py

from sys import stdin

input = stdin.readline

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

A.sort()
BC.sort(key=lambda x:x[1])

for b, c in reversed(BC):
    for i in range(b):
        if A[i] < c:
            A[i] = c
        else:
            break
    else:
        A.sort()
        continue
    break

print(sum(A))


### FIXED CODE ###

#ABC127D-IntegerCards.py

from sys import stdin

input = stdin.readline

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

List = A + BC

List.sort(key=lambda x:x[1])
sumList = []

for b, c in reversed(List):
    for i in range(b):
        if len(sumList) < N:
            sumList.append(c)
        else:
            break
    else:
        continue
    break

print(sum(sumList))
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
r, c, k = map(int, input().split())
dp = [[[0 for _ in range(3)] for _ in range(c + 5)] for _ in range(r + 5)]
pt = [[0 for _ in range(c + 5)] for _ in range(r + 5)]

for i in range(k):
    r1, c1, v = map(int, input().split())
    dp[r1][c1][0] = v
    pt[r1][c1] = v

for i in range(1, r + 1):
    for j in range(1, c + 1):
        for k in range(3):
            if k == 0:
                dp[i][j][k] = max(dp[i - 1][j][2] + pt[i][j], dp[i][j - 1][0])
            elif k == 1:
                dp[i][j][k] = max(dp[i][j - 1][0] + pt[i][j],
                                  max(dp[i][j - 1][1], dp[i][j][0]))
            else:
                dp[i][j][k] = max(dp[i][j - 1][1] + pt[i][j],
                                  max(dp[i][j - 1][2], dp[i][j][1]))

print(dp[r][c][2])

# デバッグ用
# for i in dp:
#     print(i)


### FIXED CODE ###

import sys
# import time
input = lambda: sys.stdin.readline().rstrip()
r, c, k = map(int, input().split())
# dp = [[[0] * 3 for _ in range(c + 5)] for _ in range(r + 5)]
pt = [[0 for _ in range(c + 5)] for _ in range(r + 5)]

for i in range(k):
    r1, c1, v = map(int, input().split())
    # dp[r1][c1][0] = v
    pt[r1][c1] = v

# start = time.time()
a = 0


def solve():
    memo = [[0] * 4 for _ in range(c + 1)]
    prev = [[0] * 4 for _ in range(c + 1)]
    for i in range(1, r + 1):
        memo, prev = prev, memo
        for j in range(1, c + 1):
            V = pt[i][j]
            memo[j][0] = max(prev[j][3], memo[j - 1][0])
            memo[j][1] = max(memo[j][0] + V, memo[j - 1][1])
            memo[j][2] = max(memo[j][1], memo[j - 1][1] + V, memo[j - 1][2])
            memo[j][3] = max(memo[j][2], memo[j - 1][2] + V, memo[j - 1][3])

            # dp[i][j][0] = max(dp[i - 1][j][2] + V, dp[i][j - 1][0])
            # dp[i][j][1] = max(dp[i][j - 1][0] + V, dp[i][j - 1][1],
            #                   dp[i][j][0])
            # dp[i][j][2] = max(dp[i][j - 1][1] + V, dp[i][j - 1][2],
            #                   dp[i][j][1])

    # process_time = time.time() - start

    # print(process_time)

    # print(dp[r][c][2])
    return memo[-1][3]





if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

def main():
    N ,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    inf = 10 **18 +1
    ok = inf
    ng = -inf

    def is_ok(arg):
        ans = 0
        for i in range(N):
            if A[i] * A[i] < arg :
                ans -= 1
            ok = N
            ng = -1
            if A[i] == 0:
                if arg > 0:
                    ans += N
            elif A[i] > 0:
                while (abs(ok - ng) > 1):
                    mid = (ok + ng) // 2
                    if A[i] * A[mid] < arg:
                        ng = mid
                    else:
                        ok = mid
                ans += ok
            else: 
                while (abs(ok - ng) > 1):
                    mid = (ok + ng) // 2
                    if A[i] * A[mid] < arg:
                        ok = mid
                    else:
                        ng = mid       
                ans += N-ok   
        ans /= 2
        return K > ans

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ng = mid
        else:
            ok = mid
    print(ng)
if __name__ == "__main__":
    main()

### FIXED CODE ###

N ,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
inf = max(A[0]**2,A[-1]**2)
ok1 = inf
ng1 = -inf
while (abs(ok1 - ng1) > 1):
    arg = (ok1 + ng1) // 2
    ans = 0
    for i in range(N):
        if A[i] * A[i] < arg :
            ans -= 1
        ok = N
        ng = -1
        if A[i] == 0:
            if arg > 0:
                ans += N
        elif A[i] > 0:
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ng = mid
                else:
                    ok = mid
            ans += ok
        else: 
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ok = mid
                else:
                    ng = mid       
            ans += N-ok   
    ans /= 2
    if K>ans:
        ng1 = arg
    else:
        ok1 = arg
print(ng1)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

A_sum = [0]
B_sum = [0]
for i in range(N):
    A_sum.append(A_sum[-1] + A[i])
for i in range(M):
    B_sum.append(B_sum[-1] + B[i])

ans = 0
for i in range(N+1):
    for j in range(M+1):
        time = A_sum[i] + B_sum[j]
        if time > K:
            break
        ans = max(i + j, ans)
print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

A_sum = [0]
B_sum = [0]
for i in range(N):
    A_sum.append(A_sum[-1] + A[i])
for i in range(M):
    B_sum.append(B_sum[-1] + B[i])

ans = 0
j_max = M
for i in range(N+1):
    for j in range(j_max, -1, -1):
        time = A_sum[i] + B_sum[j]
        if time > K:
            continue
        j_max = j
        ans = max(i + j, ans)
        break
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split()))
for ki in k:
    D=M=DM=C=0
    for i in range(n):
        if s[i] == "D":
            D += 1
        elif s[i] == "M":
            M += 1
            DM += D
        elif s[i] == "C":
            C += DM
        if i >= ki-1:
            j = i-ki+1
            if s[j] == "D":
                D -= 1
                DM -= M
            elif s[j] == "M":
                M -= 1
    print(C)

### FIXED CODE ###

# コピペ https://atcoder.jp/contests/dwacon5th-prelims/submissions/7670569
# 自分の https://atcoder.jp/contests/dwacon5th-prelims/submissions/7822126
# とほぼ変わらないのに自分のものはTLEするので検証
n=int(input())
s=input()
q=int(input())
for i in list(map(int,input().split())):
    a=0
    v=[0,0,0]
    for j in range(n):
        if s[j]=="D":
            v[0]+=1
        elif s[j]=="M":
            v[1]+=1
            v[2]+=v[0]
        if j>=i:
            if s[j-i]=="D":
                v[0]-=1
                v[2]-=v[1]
            elif s[j-i]=="M":
                v[1]-=1
        if s[j]=="C":
            a+=v[2]
    print(a)
### BUGGY CODE ###

n = int(input())
ans = 1
nums = list(map(int, input().split()))
for num in nums:
    ans *= num
if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

def main():
    n = int(input())
    nums = list(map(int, input().split()))
    s = set(nums)
    if 0 in s:
        print(0)
        return
    ans = 1
    bound = 10 ** 18
    for num in nums:
        ans *= num
        if ans > bound:
            print(-1)
            return
    print(ans)

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

import numpy as np
N,K=map(int, input().split())

A=list(map(int, input().split()))
for k in range(K):
    B=[0]*(N+1)
    for i in range(N):
        a=A[i]
        start=max(0,i-a)
        end=min(N,i+a+1)
        B[start]+=1
        B[end]-=1
    B=np.array(B)
    B=np.cumsum(B)[:N]
    #print(B)
    A=B.copy()
    if B.min()==N:
        break
print(*B)

### FIXED CODE ###

#import numpy as np
N,K=map(int, input().split())

A=list(map(int, input().split()))
#K=min(K, 30)
for k in range(K):
    B=[0]*(N+1)
    for i in range(N):
        a=A[i]
        start=max(0,i-a)
        end=min(N,i+a+1)
        B[start]+=1
        B[end]-=1
    #B=np.array(B)
    A=[0]*N
    A[0]=B[0]
    for i in range(1,N):
        A[i]=A[i-1]+B[i]

    if min(A)==N:
        break
    #print(B)
    
    
print(*A)
### BUGGY CODE ###

n,w=list(map(int, input().split()))
wv =[]
sum_w = 0
sum_v = 0
for i in range(n):
    wv_1 = list(map(int, input().split()))
    wv.append(wv_1)
    sum_w += wv_1[0]
    sum_v += wv_1[1]

dp = [[float("inf") for _ in  range(sum_v+1)] for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(sum_v+1):
        if j - wv[i][1] >= 0:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]] + wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]

for i,name in enumerate(dp[n][::-1]):
    if name <= w:
        break

print(sum_v - i)

### FIXED CODE ###

n,w = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]

v = sum(list(map(lambda x: x[1], wv)))
dp = [[float("inf")]*(v+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    a = wv[i]
    for j in range(v+1):
        if a[1] <= j:
            dp[i+1][j] = min(dp[i][j], dp[i][j- a[1]] + a[0])
        else:
            dp[i+1][j] = dp[i][j]

dpl = dp[-1]
for i in range(v, -1, -1):
    if dpl[i] <= w:
        print(i)
        break
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
list_st = []
for i in range(N):
  list_st.append(A.index(i+1)+1)
for i in range(N):
  print(list_st[i])

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
B = [0]*n
for i in range(n):
  B[A[i]-1] = i + 1 
for i in range(n):
  print(B[i])
### BUGGY CODE ###

import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7
    lcm_of_all_a = functools.reduce(lambda x, y: lcm(x, y), a, 1)
    b = map(lambda x: (lcm_of_all_a // x) % mode, a)
    return sum(b) % mode


def write(result):
    print(result)


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


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


if __name__ == '__main__':
    # unittest.main()
    solve()

### FIXED CODE ###

import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7

    lcm_of_all_a = 1
    for e in a:
        lcm_of_all_a = lcm(lcm_of_all_a, e)

    lcm_of_all_a %= mode
    result = 0
    for e in a:
        result += lcm_of_all_a * inverse(e, mode) % mode
        result %= mode
    return result


def write(result):
    print(result)


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


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


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

import math
from functools import reduce

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

K=int(input())
a=[]
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            a.append(gcd(i,j,k))
print(sum(a))

### FIXED CODE ###

import math
from functools import reduce

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

K=int(input())
a=[]
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            a.append(gcd(i,j,k))
print(sum(a))
### BUGGY CODE ###

L=[i for i in range(2,10**5)]
X=int(input())
while X > L[0]:
  L=list(filter(lambda x: x & L[0], L))
print(L[0])

### FIXED CODE ###

def is_prime(x):
  if x <= 1: return false
  i=2
  while i*i <= x:
    if not x%i: return False
    i+=1
  return True
 
X=int(input())
while not is_prime(X):
  X+=1
print(X)
### BUGGY CODE ###

from itertools import dropwhile as dw

D,G = map(int, input().split(' '))
p_dict = {}
op = []
for i in range(D):
    j, k = map(int, input().split(' '))
    op += [100*(i+1)] * j
    p_dict[i] = (j, k)

leng = len(op)
min_op = 10 ** 8
for i in range(2 ** leng):
    op_list = op.copy()
    for j in range(leng):
        if ((i >> j) & 1):
            op_list[-1*(j+1)] = 0
    result = sum(op_list)
    op_list.sort()
    count = len(list(dw(lambda x: x == 0, op_list)))
    for k in p_dict.keys():
        if op_list.count(100*(k+1)) == p_dict[k][0]:
            result += p_dict[k][1]
    if result >= G and count < min_op:
        min_op = count
print(min_op)









### FIXED CODE ###

import sys
import math

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

d,g = nm()
comp = [nl() for _ in range(d)]
ans = 10**10
check = set([i for i in range(d)])
for i in range(2**d):
    res = 0
    times = 0
    visited = set()
    for j in range(d):
        if (i >> j) & 1:
            res += 100 * (j+1)*comp[j][0] + comp[j][1]
            times += comp[j][0]
            visited.add(j)
    if res < g:
        ma = max(check-visited)
        waru =  100 * (ma+1)
        waru_times = math.ceil((g-res)/waru)
        res += 100*waru_times*waru
        if waru_times > comp[ma][0]-1 or res < g:
            continue
        times += waru_times
        if ans > times:
            ans = times
    elif res >= g:
        if ans > times:
            ans = times
print(ans)