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

X,Y,Z,K=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
C=[int(i) for i in input().split()]
A.sort(key=lambda x:-x)
B.sort(key=lambda y:-y)
C.sort(key=lambda z:-z)
pri=[]
primemo={}
def dp(l):
  return A[l[0]]+B[l[1]]+C[l[2]]

def priq(a,b,c):
  if [a,b,c] not in pri:
    for i in range(len(pri)):
      if dp(pri[i])<dp([a,b,c]):
        pri.insert(i,[a,b,c])
        return
    pri.append([a,b,c])

pri.append([0,0,0])
for i in range(K):
  x,y,z=pri.pop(0)
  print(dp([x,y,z]))
  if x<X-1:
    priq(x+1,y,z)
  if y<Y-1:
    priq(x,y+1,z)
  if z<Z-1:
    priq(x,y,z+1)



### FIXED CODE ###

import heapq
X,Y,Z,K=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
C=[int(i) for i in input().split()]
A.sort(key=lambda x:-x)
B.sort(key=lambda y:-y)
C.sort(key=lambda z:-z)
pri=[]
def dp(x,y,z):
  return A[x]+B[y]+C[z]

def priq(a,b,c):
  d=-dp(a,b,c)
  if tuple([d,a,b,c]) not in pri:
    heapq.heappush(pri,(d,a,b,c))

heapq.heappush(pri,(-dp(0,0,0),0,0,0))

for i in range(K):
  d,x,y,z=heapq.heappop(pri)
  print(-d)
  if x<X-1:
    priq(x+1,y,z)
  if y<Y-1:
    priq(x,y+1,z)
  if z<Z-1:
    priq(x,y,z+1)
### BUGGY CODE ###

def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c
    
N = int(input())
P = input()
I = P.count("1")
Df = int(P,2)
Ans = [0] * (N+1)
#print(solve(N,cnt))

for i in range(1, N+1):
    p = popcnt(i)
    tmp = i % p
    Ans[i] = Ans[tmp] +1 
#print("Ans = ", Ans)

for i in range(N-1):
    if P[i] == "1":
        tmp = Df - pow(2,N-i-1)
        cur = I - 1
    else:
        tmp = Df + pow(2,N-i-1)
        cur = I + 1 
    if cur == 0:
        print(0)
        continue
    print(Ans[tmp%cur]+1)

if P[N-1] == "1":
    tmp = Df - 1
    cur = I - 1
else:
    tmp = Df + 1
    cur = I + 1
if cur == 0:
    print(0)
else:
    print(Ans[tmp%cur]+1)

### FIXED CODE ###

N = int(input())
x = input()

cnt_x = x.count("1")
px10 = 0
nx10 = 0
ans = [0] * (N+1)

for i in range(1, N+1): #Nまで先に出しておく
    popcnt = format(i,"b").count("1")
    fx = i % popcnt
    ans[i] = ans[fx] + 1

for i in range(N):
    px10 += (int(x[i]) * pow(2,N-1-i, cnt_x+1)) % (cnt_x+1)#0⇒1となった場合の合計
    if cnt_x != 0 and cnt_x != 1:
        nx10 += int(x[i])*pow(2,N-1-i,cnt_x-1) % (cnt_x-1)#1⇒0となった場合の合計
#print(px10)
#print(nx10)
for i in range(N):
    if x[i] == "0":
        xi10 = (px10+pow(2,N-1-i,cnt_x+1))%(cnt_x+1)
        print(ans[xi10]+1)
    else:
        if cnt_x != 1:
            xi10 = (nx10-pow(2,N-1-i,cnt_x-1))%(cnt_x-1)
            print(ans[xi10]+1)
        else:
            print(0)
### BUGGY CODE ###

import sys
h, w = map(int, sys.stdin.readline().split())
dp = [[0] * w for _ in range(h)]
G = [list(map(int, i.split())) for i in sys.stdin.readlines()]
for x in range(h):
    dp[x][0] = 1 if G[x][0] == 0 else 0
for y in range(w):
    dp[0][y] = 1 if G[0][y] == 0 else 0
for i in range(1, h):
    for j in range(1, w):
        if(G[i][j] == 0):
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
print(max(sum(dp, [])) ** 2)

### FIXED CODE ###

import sys
import itertools
h, w = map(int, sys.stdin.readline().split())
dp = [[0] * w for _ in range(h)]
G = [[int(j) for j in sys.stdin.readline().split()] for _ in range(h)]
for x in range(h):
    dp[x][0] = 1 if G[x][0] == 0 else 0
for y in range(w):
    dp[0][y] = 1 if G[0][y] == 0 else 0
for i in range(1, h):
    for j in range(1, w):
        if(G[i][j] == 0):
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
print(max(max(i) for i in dp) ** 2)
### BUGGY CODE ###

import sys

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

import bisect

ABs = [[] for _ in range(M + 1)]
for i in range(N):
    A, B = map(int, input().split())
    if A <= M:
        bisect.insort_left(ABs[A], B)

As = 0
for i in range(M + 1):
    if i > 0:
        for b in ABs[i]:
            bisect.insort_left(ABs[0], b)
    if len(ABs[0]) > 0:
        As += ABs[0].pop(-1)
print(As)

### FIXED CODE ###

import sys

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

import bisect

ABs = [[] for _ in range(M + 1)]
for i in range(N):
    A, B = map(int, input().split())
    if A <= M:
        ABs[A].append(B)
ABs[0].sort()

As = 0
for i in range(M + 1):
    if i > 0:
        for b in ABs[i]:
            bisect.insort_left(ABs[0], b)
    if len(ABs[0]) > 0:
        As += ABs[0].pop()
print(As)
### BUGGY CODE ###

N=int(input())
A=[]
for i in range(N):
  a=int(input())
  A.append(a)
res=sorted(A)

ans=0
for j,k in enumerate(res):
  cnt=A.index(k)
  if abs(j-cnt)%2==1:
    ans+=1

print(ans//2)

### FIXED CODE ###

N=int(input())
A=[]
for i in range(N):
  a=int(input())
  A.append(a)
res=sorted(A)

def binary_search(x):
  l=0
  r=N-1

  while True:
    mid=(l+r)//2
    if res[mid]==x:
      return mid
    elif res[mid]>x:
      r=mid-1
    elif res[mid]<x:
      l=mid+1

ans=0
for j,k in enumerate(A):
  cnt=binary_search(k)
  if abs(j-cnt)%2==1:
    ans+=1

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

N,Q=map(int,input().split())
S=input()

lis = []
for i in range(len(S)-1):
  if S[i:i+2] == 'AC':
    lis += [i]

for _ in range(Q):
  L = tuple(map(int, input().split()))

  c = 0
  for l in lis:
    if L[0] - 1 <= l < L[1] - 1:
      c+=1
      
  
  print(c)


### FIXED CODE ###

N,Q=map(int,input().split())
S=input()

lis = [0] * len(S)
for i in range(len(S)):

  if i>0:
    lis[i] += lis[i-1]
  if i < len(S)-1 and S[i] == 'A' and S[i+1] == 'C':
    lis[i+1] += 1


for _ in range(Q):
  L = tuple(map(int, input().split()))

  c = 0
  print(lis[L[1]-1]-lis[L[0]-1])
### BUGGY CODE ###

#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

N, W = map(int, input().split())
WV = [[0,0]]+[ list(map(int, input().split())) for _ in range(N) ]

#p(WV)

dp = [[0 for w in range(W+1)] for _r in range(N+1)]

#print(dp)

for iN in range(1,N+1):
	w,v = WV[iN]
	for iW in range(W+1):
		
		v0 =     dp[iN-1][iW]
		v1 = v + dp[iN-1][iW-w] if iW-w>=0 else 0
		#p("w,v,v0,v1, ",w,v,v0,v1)
		
		dp[iN][iW] = max(v0, v1)

#p(dp)

print(dp[-1][-1])

### FIXED CODE ###

#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

N, W = map(int, input().split())
WV = [[0,0]]+[ list(map(int, input().split())) for _ in range(N) ]

#p(WV)

dp = [[0 for w in range(W+1)] for _r in range(N+1)]

#print(dp)

for iN in range(1,N+1):
	w,v = WV[iN]
	for iW in range(W+1):
		
		v0 =     dp[iN-1][iW]
		v1 = v + dp[iN-1][iW-w] if iW-w>=0 else 0
		#p("w,v,v0,v1, ",w,v,v0,v1)
		
		dp[iN][iW] = max(v0, v1)

#p(dp)

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

N, M, Q = map(int, input().split())
matrix = [[0]*(N+1) for _ in range(N)]

for _ in range(M):
    l, r = map(int, input().split())
    matrix[l-1][r] += 1

for i in range(N):
    for j in range(1, N+1):
        matrix[i][j] += matrix[i][j-1]

for _ in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p-1, q):
        ans += matrix[i][q]-matrix[i][p-1]
    print(ans)

### FIXED CODE ###

N, M, Q = map(int, input().split())
matrix = [[0]*(N+1) for _ in range(N)]

for _ in range(M):
    l, r = map(int, input().split())
    matrix[l-1][r] += 1

for i in range(N):
    for j in range(1, N+1):
        matrix[i][j] += matrix[i][j-1]

for _ in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p-1, q):
        ans += matrix[i][q]-matrix[i][p-1]
    print(ans)
### BUGGY CODE ###

n, w = map(int,input().split())
li = []
while True:
    try:
        li.append(list(map(int,input().split())))
    except:
        break

dp=[[0] * (w+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1,w+1):
        if (j-li[i-1][0]>=0):
            # 品物がひとつ前で重さは同じ所の価値と品物がひとつ前で重さが加える価値を持し品物の重さ分引いたときの価値にひとつ前の品物の価値を加えたもの
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-li[i-1][0]]+li[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n][w])

### FIXED CODE ###

n, w = map(int,input().split())
li = []
while True:
    try:
        li.append(list(map(int,input().split())))
    except:
        break

dp=[[0] * (w+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1,w+1):
        if (j-li[i-1][0]>=0):
            # 品物がひとつ前で重さは同じ所の価値と品物がひとつ前で重さが加える価値を持し品物の重さ分引いたときの価値にひとつ前の品物の価値を加えたもの
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-li[i-1][0]]+li[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n][w])
### BUGGY CODE ###

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
f = [int(x) for x in input().split()]
a.sort()
f.sort(reverse=True)
lx = 0
rx = 10 ** 12
for i in range(1000):
    if lx == rx:
        break
    cx = (lx + rx) // 2
    kk = 0
    for j in range(n):
        ta = a[j]
        while(ta*f[j] > cx):
            ta -= 1
            kk += 1
    if kk <= k:
        rx = cx
    else:
        lx = cx
print(rx)

### FIXED CODE ###

n, k = map(int, input().split())
# a = [int(x) for x in input().split()]
# f = [int(x) for x in input().split()]
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse=True)
lx = -1
rx = a[-1] * f[0]
while rx-lx>1 :
    cx = (lx + rx) // 2
    kk = 0
    for j in range(n):
        kk += max(0, a[j] - cx//f[j])
    if kk <= k:
        rx = cx
    else:
        lx = cx
print(rx)
### BUGGY CODE ###

s = input()
t = input()

dp = [[0]*(len(t)+1) for i in range(len(s)+1)]

for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j]+1
    else:    
      dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
           
ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0 :
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] +ans
        i -= 1
        j -= 1
print(ans)


### FIXED CODE ###

s = input()
t = input()

dp = [[0]*(len(t)+1) for i in range(len(s)+1)]

for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j]+1
    else:    
      dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
           
ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0 :
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] +ans
        i -= 1
        j -= 1
print(ans)
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
listx = [int(i) for i in input().split()]
listy = [int(i) for i in input().split()]
listz = [int(i) for i in input().split()]

listxy = []
for i in range(0,x):
    for j in range(0,y):
        listxy.append(listx[i]+listy[j])
listxy.sort()
#print(listxy)
if x*y>k:
    listxy=listxy[-k:]
    listxyz = []
    for i in range(0,k):
        for j in range(0,z):
            listxyz.append(listxy[i]+listz[j])
else:
    listxyz = []
    for i in range(0,x*y):
        for j in range(0,z):
            listxyz.append(listxy[i]+listz[j])

listxyz.sort()
if len(listxyz)>k:
    listxyz=listxyz[-k:]
for i in range(0,k):
    print(listxyz[-(i+1)])
    

### FIXED CODE ###

X,Y,Z,K = map(int,input().split())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A.sort(reverse=True)
A = A[0:K]
B.sort(reverse=True)
B = B[0:K]
AB = [a+b for a in A for b in B]

AB.sort(reverse=True)

AB = AB[0:K]

C.sort(reverse=True)
C=C[0:K]
ABC = [ab+c for ab in AB for c in C]

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

import numpy as np

N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))
dp = np.array([[0 for j in range(W+1)] for _ in range(N+1)])
for i in range(1, N+1):
    w, v = items[i-1]
    dp[i, :w] = dp[i-1, :w]
    dp[i, w:] = np.maximum(dp[i-1, :-w] + v, dp[i-1, w:])
print(dp[N, W])

### FIXED CODE ###

from collections import defaultdict
from itertools import product, accumulate

N, W = map(int, input().split())
items = defaultdict(list)
for _ in range(N):
    w, v = map(int, input().split())
    items[w].append(v)
weights = list(items.keys())
nums = {w: len(items[w]) for w in weights}
cumsum = {w: None for w in weights}
for i, w in enumerate(weights):
    items[w].sort(reverse=True)
    cumsum[w] = [0] + list(accumulate(items[w]))
ans = 0
for tup in product(*[range(nums[w] + 1) for w in weights]):
    temp_weight = sum(w * t for w, t in zip(weights, tup))
    if temp_weight > W: continue
    temp_value = sum(cumsum[w][t] for w, t in zip(weights, tup))
    ans = max(temp_value, ans)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
import functools
import operator
B=functools.reduce(operator.mul, A)
print(-1 if B>10**18 else B)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
r=1
if 0 in A:
    r=0
for n in A:
    r=r*n
    if r>10**18:
        r=-1
        break
print(r)
### BUGGY CODE ###


def main():
    n =int( input())
    sn=[]
    for i in range(n):
        
        inWord = str(input())
        addFlag = True
        for s in sn:
            if s["word"] == inWord and len(sn) !=0:
                s["count"]+=1
                addFlag = False
                break
        if addFlag ==True:
            sn.append( {"word":inWord,"count":1})
        
    a= sorted(sn, reverse=True,key=lambda x:x['count'])
    most = a[0]["count"]

    mostWords=[]
    for elm in a:
        if elm["count"] == most:
            mostWords.append(elm["word"])
        
    mostWords.sort()

    for elm in mostWords:
        print(elm)
    return

main()



### FIXED CODE ###

def main():
    n =int( input())

    cnt=dict()
    
    for _ in range(n):
        s=input()
        if s in cnt:
            cnt[s]+=1
        else :
            cnt[s]=1
    #print(cnt)
    
    num = 0
    res =[]
    for key,value in cnt.items():
        #print(key,":::",value)
        if value > num:
            num=value
            res=[]
            res.append(key)

        elif value==num:
            res.append(key)

    #print("res::",res)

    
    #a = [k for k, v in cnt.items() if v == max(cnt.values())]


    #print("結果発表：：：：",len(res))
    res.sort()
    for elm in res:
        print(elm)


main()
### BUGGY CODE ###

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

for i in range(n):
    s *= a[i]
    if 0 in a and s > 10**18:
        print(0)
        break
    elif 0 != a and s > 10**18:
        print(-1)
        break
    
if s <= 10**18:
    print(s)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
s = 1
f = 1
if 0 in a:
    print(0)
else:
    for i in a:
        s *= i
        if s > 10**18:
            print(-1)
            break
            
    if s <= 10**18:
        print(s)
### BUGGY CODE ###

n = int(input())
s = input()
r = []
g = []
b = []

for i in range(n):
  if s[i] == 'R':
    r.append(i)
  elif s[i] == 'G':
    g.append(i)
  else:
    b.append(i)
res = 0
if max(len(r),len(g),len(b)) == len(r):
  for i in g:
    for j in b:
      flg = 0
      if (i + j) / 2 in r:
        flg += 1
      if 2 * i - j in r:
        flg += 1
      if 2 * j - i in r:
        flg += 1
      res += len(r) - flg
else:
  for i in g:
    for j in r:
      flg = 0
      if (i + j) / 2 in b:
        flg += 1
      if 2 * i - j in b:
        flg += 1
      if 2 * j - i in b:
        flg += 1
      res += len(b) - flg
print(res)


### FIXED CODE ###

n=int(input())
s=input()
R=[]
G={}
B=[]
for i in range(n):
  if s[i]=='R':
    R.append(i+1)
  elif s[i]=='G':
    G[i+1]=G.get(i+1,0)+1
  else:
    B.append(i+1)
res=len(R)*len(G)*len(B)
for i in R:
  for j in B:
    if ((i+j)%2==0 and G.get((i+j)//2,0)==1):
      res-=1
    if G.get(2*max(i,j)-min(i,j),0)==1:
      res-=1
    if G.get(2*min(i,j)-max(i,j),0)==1:
      res-=1
print(res)
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
for i in range(n):
	a[i]=format(a[i],'b')
#count1に1をカウントして入れる
#popは右側に行うとはやいらしいので気にせず行う
total=0
count1=0
for k in range(60):
	count1=0
	for i in range(n):
		if k<len(a[i]):
			if a[i][-1-k]=='1':
				count1+=1
	total+=count1*(n-count1)*(2**k)
	total=total%(10**9+7)
print(total)

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
for i in range(n):
	a[i]=format(a[i],'b')
#count1に1をカウントして入れる
#popは右側に行うとはやいらしいので気にせず行う
total=0
count1=0
for k in range(60):
	count1=0
	for i in range(n):
		if k<len(a[i]):
			if a[i][-1-k]=='1':
				count1+=1
	total+=count1*(n-count1)*(2**k)
	total=total%(10**9+7)
print(total)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for i in range(n):
    for j in range(i,n):
        if sum(a[i:j+1]) % m == 0:
            count += 1
print(count)

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = (cum[i] + a[i]) % m
d = {}
for i in cum:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
ans = 0
for i, count in d.items():
    ans += count * (count - 1) // 2
print(ans)
### BUGGY CODE ###

import math

N,K=map(int,input().split())
S=input()
L=[]
seq=0
prev='2'
for i in S:
  if i == prev:
    seq += 1
  else:
    L.append(seq)
    prev = i
    seq = 1
L.append(seq)
L.append(0)

L_cum = [0]*(len(L)+1)
for i in range(len(L)):
  L_cum[i]=sum(L[0:i+1])

if S[0] == '0':
  num_0 = math.ceil((len(L)-2)/2)
  if num_0<=K:
    ans=N
  else:
    rev=[0]*(num_0-K+1)
    for i in range(num_0-K+1):
      rev[i]=L_cum[2*(K+i)]-L_cum[i*2-1]
    ans=max(rev)
else:
  num_0 = math.floor((len(L)-2)/2)
  if num_0<=K:
    ans=N
  else:
    rev=[0]*(num_0-K+1)
    for i in range(num_0-K+1):
      rev[i]=L_cum[2*(K+i)+1]-L_cum[2*i]
    ans=max(rev)
print(ans)

### FIXED CODE ###

import math

N,K=map(int,input().split())
S=input()
L=[]
seq=0
prev='2'
for i in S:
  if i == prev:
    seq += 1
  else:
    L.append(seq)
    prev = i
    seq = 1
L.append(seq)
L.append(0)

L_cum = [0]*(len(L)+1)
for i in range(len(L)):
  L_cum[i]=L_cum[i-1]+L[i]

if S[0] == '0':
  num_0 = math.ceil((len(L)-2)/2)
  if num_0<=K:
    ans=N
  else:
    rev=[0]*(num_0-K+1)
    for i in range(num_0-K+1):
      rev[i]=L_cum[2*(K+i)]-L_cum[i*2-1]
    ans=max(rev)
else:
  num_0 = math.floor((len(L)-2)/2)
  if num_0<=K:
    ans=N
  else:
    rev=[0]*(num_0-K+1)
    for i in range(num_0-K+1):
      rev[i]=L_cum[2*(K+i)+1]-L_cum[2*i]
    ans=max(rev)
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
 
H,W = map(int,input().split())
maze = [list(input())for i in range(H)]
que = deque([])
 
for i in range(H):
  for j in range(W):
    if maze[i][j] == "#":
      que.append([i,j])
      maze[i][j]=0      

patterns = [[1,0],[-1,0],[0,1],[0,-1]]
while que:
  now = que.popleft()
  nowY = now[0]
  nowX = now[1]
  nowStep = maze[nowY][nowX]
  for pattern in patterns:
    nextY = nowY + pattern[0]
    nextX = nowX + pattern[1]
    nextStep = nowStep + 1
    if 0 <= nextY < H and 0 <= nextX < W and maze[nextY][nextX]==".":
      maze[nextY][nextX]=nextStep
      que.append([nextY,nextX])
      
print(nowStep)

### FIXED CODE ###

import numpy as np
h,w=map(int,input().split())
maze = []
for i in range(h):
  maze.append([0 if x=="#" else float('INF') for x in list(input())])
maze = np.array(maze)

for i in range(1,h):
  maze[i,:] = np.minimum(maze[i,:],maze[i-1,:]+1)
for j in range(h-2,-1,-1):
  maze[j,:] = np.minimum(maze[j,:],maze[j+1,:]+1)
for k in range(1,w):
  maze[:,k] = np.minimum(maze[:,k],maze[:,k-1]+1)
for l in range(w-2,-1,-1):
  maze[:,l] = np.minimum(maze[:,l],maze[:,l+1]+1)


print(int(np.max(maze)))
### BUGGY CODE ###

import math

D,G = map(int,input().split())
p = []
c = []
for i in range(D):
        p_tmp,c_tmp = map(int,input().split())
        p.append(p_tmp)
        c.append(c_tmp)

ans = sum(p)
for i in range(D):
        for j in range(p[i]):
                for k in range(2**D-1):
                        score = (i+1)*100*j
                        ans_tmp = j
                        for l in range(D):
                                if l == i:
                                        continue
                                elif (k>>l)%2 == 1:
                                        score += (l+1)*100*p[l]+c[l]
                                        ans_tmp += p[l]
                        if score >= G:
                                ans = min(ans,ans_tmp)

print(ans)

### FIXED CODE ###

import math
D,G = map(int,input().split())
p=[]
c=[]
for i in range(D):
    p_tmp,c_tmp = map(int,input().split())
    p.append(p_tmp)
    c.append(c_tmp)

ans = sum(p)
for i in range(2**D):
    score_tmp = 0
    ans_tmp = 0
    for j in range(D):
        if (i>>j)%2 == 1:
            score_tmp += p[j]*(j+1)*100+c[j]
            ans_tmp += p[j]

    if ans_tmp >= ans:
        continue
    elif score_tmp >= G:
        ans = ans_tmp
        continue
    else:
        for j in range(D):
            if (i>>(D-1-j))%2 == 1:
                continue
            elif score_tmp + p[D-1-j]*(D-j)*100 < G:
                break
            else:
                ans_tmp += math.ceil((G - score_tmp)/((D-j)*100))
                ans = min(ans,ans_tmp)
                break

print(ans)