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

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [list(map(int, readline().strip())) for j in range(H)]

    white = 0
    for line in S:
        white += sum(line)

    if white <= K:
        print(0)
        exit()

    ans = 10**5
    for i in range(2**(H-1)):
        impossible = False
        x = 0
        ly = bin(i).count("1")
        y_sum = [0]*(ly + 1)
        j = 0
        while j < W:
            m = 0
            y = [0]*(ly + 1)
            for k in range(H):
                if S[k][j] == 1:
                    y[m] += 1
                    if y[m] > K:
                        impossible = True
                        break
                    y_sum[m] += 1
                    if y_sum[m] > K:
                        x += 1
                        y_sum = [0]*(ly + 1)
                        j -= 1
                        break
                if (i >> k) & 1:
                    m += 1
            j += 1
            if impossible:
                x = 10**6
                break

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [readline().strip() for j in range(H)]

    white = []
    for line in S:
        white.append(line.count("1"))
    white_total = sum(white)

    if white_total <= K:
        print(0)
        exit()

    ans = 10**5
    for i in range(2**(H-1)):
        impossible = False
        x = 0
        ly = bin(i).count("1")
        y_sum = [0]*(ly + 1)
        j = 0
        while j < W:
            m = 0
            y = [0]*(ly + 1)
            for k in range(H):
                if S[k][j] == "1":
                    y[m] += 1
                    if y[m] > K:
                        impossible = True
                        break
                    y_sum[m] += 1
                    if y_sum[m] > K:
                        x += 1
                        y_sum = [0]*(ly + 1)
                        j -= 1
                        break
                if (i >> k) & 1:
                    m += 1
            j += 1
            if impossible:
                x = 10**6
                break

        ans = min(ans, x + ly)

    print(ans)


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

N = int(input())
c = [set([]) for _ in range(N + 1)]
g = [[0] * (N + 1) for _ in range(N + 1)]
paths = []
for _ in range(N-1):
    a, b = map(int, input().split())
    paths.append((a, b))

cmax = 1

for a, b in paths:
    cnt = 1
    while True:
        if cnt not in c[a] and cnt not in c[b]:
            c[a].add(cnt)
            c[b].add(cnt)
            g[a][b] = cnt
            cmax = max(cmax, cnt)
            break
        cnt += 1

print(cmax)
for a, b in paths:
    print(g[a][b])


### FIXED CODE ###

from collections import deque

N = int(input())
g = [[] for _ in range(N)]
vp = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    vp.append((a, b))

k = 0
d = dict()
cs = [0] * N
used = [False] * N

que = deque([])
used[0] = 1
que.appendleft(0)
while len(que) > 0:
    v = que.pop()
    k = max(k, len(g[v]))
    cur = 1
    for u in g[v]:
        if used[u]:
            continue
        if cur == cs[v]:
            cur += 1
        cs[u] = d[(u, v)] = d[(v, u)] = cur
        cur += 1
        used[u] = True
        que.appendleft(u)
print(k)
for p in vp:
    print(d[p])
### BUGGY CODE ###

import itertools
N, K = list(map(int, input().split()))
count = 0
poss = [n for n in range(1, N+1) if (2*n)%K==0]

poss2 = list(itertools.product(poss, repeat=3))

def c(data):
    global count
    if (data[0]+data[1])%K==0 and (data[1]+data[2])%K==0:
        count += 1

for comb in poss2:
    c(comb)

print(count)

### FIXED CODE ###

N, K = map(int, input().split())
num = {i%K:N//K for i in range(1, K+1)}
mod = N % K
for i in range(1, mod+1):
    num[i] += 1

ans = 0
for i in range(K):
    if (2*i) % K == 0:
        cnt = num[i]
        cnt *= num[(K-i)%K] * num[(K-i)%K]
        ans += cnt
print(ans)
### BUGGY CODE ###

import itertools

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

dp = [[[0 for _ in range(a * n + 1)] for _ in range(n + 1)]
      for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(1, n+1):
    for j in range(n+1):
        for k in range(a * n + 1):
            dp[i][j][k] = dp[i-1][j][k]
            if j > 0 and k - xs[i-1] >= 0:
                dp[i][j][k] += dp[i-1][j-1][k-xs[i-1]]


c = 0
for j in range(1, n+1):
    c += dp[n][j][j * a]

print(c)

### FIXED CODE ###

import itertools

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

dp = [[[0 for _ in range(a * n + 1)] for _ in range(n + 1)]
      for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(1, n+1):
    for j in range(n+1):
        for k in range(a * n + 1):
            dp[i][j][k] = dp[i-1][j][k]
            if j > 0 and k - xs[i-1] >= 0:
                dp[i][j][k] += dp[i-1][j-1][k-xs[i-1]]


c = 0
for j in range(1, n+1):
    c += dp[n][j][j * a]

print(c)
### BUGGY CODE ###

from collections import Counter

n = int(input())
li = list(map(int,input().split()))
a = [l for i,l in enumerate(li) if i % 2 == 0]
b = [l for i,l in enumerate(li) if i % 2 == 1]
se_a = list(set(a))
se_b = list(set(b))
all_lis = []
for aa in se_a:
    tmp_cnt = len(a) - Counter(a)[aa]
    #print(tmp_cnt,len(a),Counter(a)[aa])
    tmp_list = []
    for bb in se_b:
        if aa == bb:
            continue
        tmp_list.append(tmp_cnt+len(b) - Counter(b)[bb])
    #print(tmp_list)
    all_lis += tmp_list
if all_lis:
    print(min(all_lis))
else:
    print(len(a))

### FIXED CODE ###

from collections import Counter
n = int(input())
li = list(map(int,input().split()))
a = [l for i,l in enumerate(li) if i % 2 == 0]
b = [l for i,l in enumerate(li) if i % 2 == 1]
se_a = list(set(a))
se_b = list(set(b))
if Counter(a).most_common()[0][0] != Counter(b).most_common()[0][0]:
    a_change = len(a) - Counter(a).most_common()[0][1]
    b_change = len(b) - Counter(b).most_common()[0][1]
    print(a_change+b_change)
else:
    if len(se_a) == 1 and len(se_b) == 1:
        print(len(a))
    else:
        x = len(a) - Counter(a).most_common()[0][1] + len(b) - Counter(b).most_common()[1][1]
        y = len(a) - Counter(a).most_common()[1][1] + len(b) - Counter(b).most_common()[0][1]
        print(min(x,y))
### BUGGY CODE ###

s = input()
q = int(input())
a = 0
for i in range(q):
    b = list(input().split())
    if b[0] == "1":
        if a == 0:
            a = 1
        else:
            a = 0
    else:
        if (a, b[1]) == (0, "1") or (a, b[1]) == (1, "2"):
            s = b[2] + s
        else:
            s = s + b[2]
if a == 0:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())
a = 0
c = ""
for i in range(q):
    b = list(input().split())
    if b[0] == "1":
        if a == 0:
            a = 1
        else:
            a = 0
    else:
        if (a, b[1]) == (0, "1") or (a, b[1]) == (1, "2"):
            s.appendleft(b[2])
        else:
            s.append(b[2])
if a == 0:
    for i in range(len(s)):
        c += s.popleft()
else:
    for i in range(len(s)):
        c += s.pop()
print(c)
### BUGGY CODE ###

from collections import deque
# from collections import Counter
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# from math import sqrt

# input = sys.stdin.readline
# def main():

#---------------------------------------------------------

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

tree = [list(map(int,input().split())) for i in range(n-1)]
ope  = [list(map(int,input().split())) for i in range(q)]

road = [[] for i in range(n)]
cnt  = [0 for i in range(n)]

for i in tree:
    i[0]-=1
    i[1]-=1
    road[i[0]].append(i[1])
    road[i[1]].append(i[0])

dist = [-1]*n
que  = deque()
dist[0] = 0
que.append(0)

while(len(que)!=0):
    # BFS/DFS
    v = que.popleft()
    for i,r in enumerate(road[v]):
        if dist[r]!=-1:
            continue
        dist[r] = dist[v] + 1
        que.append(r)

for i in ope:
    for j in range(n):
        if j == i[0]-1:
            cnt[j] += i[1]
        if dist[j] > dist[i[0]-1]:
            cnt[j] += i[1]

print(*cnt)

### FIXED CODE ###

from collections import deque
# from collections import Counter
# from itertools import accumulate
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# from math import sqrt

# input = sys.stdin.readline
# def main():

#---------------------------------------------------------

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

road = [[] for _ in range(n)]
cnt  = [0 for _ in range(n)]

for i in range(n-1):
    a,b = map(int,input().split())
    road[a-1].append(b-1)
    road[b-1].append(a-1)

for i in range(q):
    idx,v = map(int,input().split())
    cnt[idx-1] += v

dist = [-1]*n
que  = deque()
dist[0] = 0
que.append(0)

while(len(que)!=0):
    # BFS/DFS
    v = que.pop()
    for r in road[v]:
        if dist[r]!=-1:
            continue
        dist[r] = dist[v] + 1
        cnt[r] += cnt[v]
        que.append(r)

print(*cnt)
### BUGGY CODE ###

n=int(input())
x=[0]*n
y=[0]*n
z=[0]*n
a=-1
b=-1
for i in range(n):
    x[i],y[i] = list(map(int, input().strip().split()))
for i in range(n):
    z[i]=x[i]**2+y[i]**2
for i in range(n):
    if z[i]==max(z):
        a=i
        break
for i in range(n):
    if z[i]==min(z):
        b=i
        break
print(abs(x[a]-x[b])+abs(y[a]-y[b]))

    
    

### FIXED CODE ###

n=int(input())
x=[0]*n
y=[0]*n
z=[]
w=[]
for i in range(n):
    x[i],y[i]= list(map(int, input().strip().split()))
    z.append(x[i]+y[i])
    w.append(x[i]-y[i])
a=max(z)-min(z)
b=max(w)-min(w)
print(max(a,b))
### BUGGY CODE ###

a = int(input())
l=list(map(int ,input().split()))
for i in range(a):
    print((l.index(i+1))+1, end=" ")

### FIXED CODE ###

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

x = int(input())

for a in range(0, 5000):
  for b in range(-5000, 0):
    if (a ** 5 - b ** 5) == x:
      print(a, b)
      exit()

### FIXED CODE ###

x = int(input())

for a in range(-150, 150):
  for b in range(-150, 150):
    if (a ** 5 - b ** 5) == x:
      print(a, b)
      exit()
### BUGGY CODE ###

N, W = map(int,input().split())
wv = [[int(x) for x in input().split()] for i in range(N)]

dp = [[float("inf") for i in range(1000*N+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for v in range(1000*N+1):
        if wv[i][1] <= v:
            dp[i+1][v] = min(dp[i][v], dp[i][v-wv[i][1]] + wv[i][0])
        else:
            dp[i+1][v] = dp[i][v]
ans = 0
for i in range(1000*N+1):
    if dp[N][i]<=W:
        ans = i
print(ans)

### FIXED CODE ###

import numpy as np
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]
 
DP = np.ones(N*1000+1, dtype=int) *(W+1)
DP[0] = 0
#総価値 i 円を得るために最低限必要な重量
for i in range(N):
    DP[v[i]:] = np.minimum(DP[:-v[i]]+ w[i], DP[v[i]:])
ans = 0
for k in range(N*1000+1):
    if DP[k] <= W:
        ans = k
        
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
color = [[], [], []]
for i in range(N):
    if S[i] == 'R':
        color[0].append(i)
    elif S[i] == 'G':
        color[1].append(i)
    elif S[i] == 'B':
        color[2].append(i)
rn = len(color[0])
gn = len(color[1])
bn = len(color[2])
mi = 0
for i in color[0]:
    for j in color[1]:
        if 2*j-i in color[2]:
            mi += 1
        if (j-i)/2+i in color[2]:
            mi += 1
        if 2*i-j in color[2]:
            mi += 1
print(rn*gn*bn-mi)

### FIXED CODE ###

N = int(input())
S = input()
color = [[], [], []]
for i in range(N):
    if S[i] == 'R':
        color[0].append(i)
    elif S[i] == 'G':
        color[1].append(i)
    elif S[i] == 'B':
        color[2].append(i)
rn = len(color[0])
gn = len(color[1])
bn = len(color[2])
mi = 0
for i in range(N):
    p = 0
    while i + 2*p <= N-1:
        if S[i] != S[i+p] and S[i+p] != S[i+2*p] and S[i] != S[i+2*p]:
           mi += 1
        p += 1
print(rn*gn*bn-mi)
### BUGGY CODE ###

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


# number_to_prime[i]: i の最小の素因数, iが素数ならば0
number_to_prime = [0] * (10**6 + 1)

# preprocess
for i in range(2, 10**6+1):
    if not number_to_prime[i]:
        j = 2
        while j*i <= 10**6:
            number_to_prime[j*i] = i
            j += 1


def is_pairwise():
    used_primes = set()
    pairwise_flag = 1
    for a in A:
        if a == 1:
            continue
        curr_primes = set()
        while number_to_prime[a]:
            prime = number_to_prime[a]
            curr_primes.add(prime)
            a //= prime
        curr_primes.add(a)
        if used_primes & curr_primes:
            pairwise_flag = 0
            break
        else:
            used_primes = used_primes | curr_primes
    return pairwise_flag

def is_setwise(*A):
    import math
    from functools import reduce

    return reduce(math.gcd, A) == 1

if is_pairwise():
    print("pairwise coprime")
elif is_setwise(*A):
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

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


# number_to_prime[i]: i の最小の素因数, iが素数ならば0
number_to_prime = [0] * (10**6 + 1)

# preprocess
for i in range(2, 10**6+1):
    if not number_to_prime[i]:
        j = 1
        while j*i <= 10**6:
            number_to_prime[j*i] = i
            j += 1

def is_pair_copr(A):
    import numpy as np
    U = 1 << 20
    div_p = np.arange(U)
    for p in range(2, U):
        if div_p[p] != p:
            continue
        div_p[p::p] = p
    used = np.zeros(U, np.bool_)
 
    for x in A:
        while x > 1:
            p = div_p[x]
            while x % p == 0:
                x //= p
            if used[p]:
                return False
            used[p] = True
    return True

def is_pairwise():
    used_primes = set()
    pairwise_flag = 1
    for a in A:
        curr_primes = set()
        while a > 1:
            prime = number_to_prime[a]
            curr_primes.add(prime)
            a //= prime
        if used_primes & curr_primes:
            pairwise_flag = 0
            break
        else:
            used_primes = used_primes | curr_primes
    return pairwise_flag

def is_setwise(*A):
    import math
    from functools import reduce

    return reduce(math.gcd, A) == 1

if is_pair_copr(A):
    print("pairwise coprime")
elif is_setwise(*A):
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

N, K = map(int,input().split())
A = sorted(map(int,input().split()))
F = sorted(map(int,input().split()),reverse=True)
low,high = -1, max(map(lambda x,y:x*y, A,F))
while high-low>1:
  mid = (high+low)//2
  k = sum([a-min(a,mid//f) for a,f in zip(A,F)])
  if k>K: low = mid
  else: high = mid
print(high)

### FIXED CODE ###

import numpy as np
N, K = map(int,input().split())
A = np.array(sorted(map(int,input().split())))
F = np.array(sorted(map(int,input().split()) ,reverse=True))
low,high = -1, int(1e12)
while high-low>1:
  mid = (high+low)//2
  k = (A-np.minimum(A,mid//F)).sum()
  if k>K: low = mid
  else: high = mid
print(high)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	B
# CreatedDate:  2020-03-07 21:09:01 +0900
# LastModified: 2020-03-07 21:20:17 +0900
#

import collections

def main():
    N,A,B = map(int,input().split())
    S=[]
    for _ in range(10**100):
        for _ in range(A):
            S.append(0)
        for _ in range(B):
            S.append(1)
        if len(S)>N:
            break
    c=collections.Counter(S[:N])
    print(c[0])




if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	B
# CreatedDate:  2020-08-30 14:36:32 +0900
# LastModified: 2020-08-30 14:45:15 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    n, a, b = map(int, input().split())
    tmp = n - n // (a+b) * (a+b)
    ans = n//(a+b) * a
    if tmp <= a:
        print(ans+tmp)
    else:
        print(ans+a)


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

import math
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[math.inf for i in range(n)]
dp[0]=0
for i in range(1,n):
    for j in range(1,k+1):
        if i-j<0:
            continue
        dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[n-1])

### FIXED CODE ###

import math
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[math.inf for i in range(n)]
dp[0]=0
for i in range(1,n):
    for j in range(1,k+1):
        if i-j<0:
            continue
        dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[n-1])
### BUGGY CODE ###

from math import *
def f(n):
    ans = 0
    r = range(1, int(sqrt(n))+1)
    return sum(x**2 + y**2 + z**2 + x*y + y*z + z*x == n for x in r for y in r for z in r)

n = int(input())
for i in range(1, n+1):
    print(f(i))

### FIXED CODE ###

n = int(input())
ans = [0]*(n+1)
r = range(1, int(n**0.5)+1)
for x in r:
    for y in r:
        for z in r:
            a = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if a<=n:
                ans[a] += 1
for i in ans[1:]:
    print(i)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
temp,i = sum(a[:k]),k+1
for _ in range(n-k):
    score = sum(a[i-k:i])
    print("Yes" if score>temp else "No")
    temp = score
    i+=1

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
temp,i = sum(a[:k]),k
for _ in range(n-k):
    score = temp+a[i]-a[i-k]
    print("Yes" if score>temp else "No")
    temp = score
    i+=1
### BUGGY CODE ###

a,b,k = map(int,input().split())
for i in range(k):
    if a >= 1:
        a -= 1
    elif b >= 1:
        b -= 1
    else:
        continue
print(str(a)+" "+str(b))

### FIXED CODE ###

a,b,k = map(int,input().split())
if k >= a:
    if k-a >= b:
        print(str(0)+" "+str(0))
    else:
        print(str(0)+" "+str(b-k+a))
else:
    print(str(a-k)+" "+str(b))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = []
flg = False
if n % 2 == 0:
    flg = True
for e in a:
    if flg:
        b.append(e)
        flg = False
    else:
        b.insert(0, e)
        flg = True
print(' '.join(map(str, b)))


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = deque([])
flg = False
if n % 2 == 0:
    flg = True
for e in a:
    if flg:
        b.append(e)
        flg = False
    else:
        b.appendleft(e)
        flg = True
print(' '.join(map(str, b)))
### BUGGY CODE ###

import heapq
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


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

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * (2 ** N)
for k in range(1, 2 ** N):
    dp[k] = {(A[0], 0), (A[k], k)}

digits = []
k = 1
while k < 2 ** N:
    digits.append(k)
    k <<= 1

for k in range(1, 2 ** N):
    dp[k] = set(heapq.nlargest(2, dp[k]))
    for d in digits:
        if k & d == 0:
            dp[k | d] |= dp[k]

ans = [0] * (2 ** N)
for k in range(1, 2 ** N):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
SIZE = 2 ** N

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * SIZE
for k in range(1, SIZE):
    dp[k] = list(sorted([(A[0], 0), (A[k], k)]))

for k in range(1, SIZE):
    mask = k
    while mask < SIZE - 1:
        # kに立ってないビットを1つだけ立てる
        next_k = (mask + 1) | k
        mask |= next_k

        a1, a2 = dp[k]
        b1, b2 = dp[next_k]
        if a1 > b2:
            # dp[next_k] = a1, a2
            dp[next_k] = dp[k]
        elif b1 > a2:
            # dp[next_k] = b1, b2
            pass
        elif a2 > b2:
            dp[next_k] = b2, a2
        elif b2 > a2:
            dp[next_k] = a2, b2

ans = [0] * SIZE
for k in range(1, SIZE):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')
### BUGGY CODE ###

INF = float('inf')
d, g = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(d)]
def f(data, total, targets):
  if total <= 0:
    return 0
  result = INF
  for i in targets:
    score = (i + 1) * 100
    t = (total + score - 1) // score
    if t < data[i][0] and t < result:
      result = t
  for i in range(len(targets)):
    j = targets[i]
    p, c = data[j]
    t = p + f(data, total - (j + 1) * 100 * p - c, targets[0:i] + targets[i + 1:])
    if t < result:
      result = t
  return result
print(f(data, g, list(range(len(data)))))


### FIXED CODE ###

INF = float('inf')
d, g = map(int, input().split())
data = []
for i in range(d):
  p, c = map(int, input().split())
  data.append([p, c, (i + 1) * 100, (i + 1) * 100 * p + c])
def f(data, total, targets):
  if total <= 0:
    return 0
  result = INF
  for i in targets:
    score = data[i][2]
    t = (total + score - 1) // score
    if t < data[i][0] and t < result:
      result = t
  for i in range(len(targets)):
    j = targets[i]
    p, c, score, subtotal = data[j]
    t = p + f(data, total - subtotal, targets[0:i] + targets[i + 1:])
    if t < result:
      result = t
  return result
print(f(data, g, list(range(len(data)))))