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

# 入力の取得
i = list(map(int, input().split()))
kazoeru = i[0]
ao = i[1]
aka= i[2]
kaisuu = i[0]/(i[1]+i[2])

number = 0
list = []

# リスト作成
while number <= kaisuu:
    # 青いボールを追加
    ball = 0
    while ball < ao:
        list.append("ao")
        ball += 1

    # 赤いボールを追加
    ball = 0
    while ball < aka:
        list.append("aka")
        ball += 1
    #回数加算
    number += 1

# 青ボールを数える
number = 0
aonokazu = 0
while number < kazoeru:
    if list[number] == "ao":
        aonokazu += 1
    number += 1

print(aonokazu)

### FIXED CODE ###

# 入力の取得
i = list(map(int, input().split()))
kazoeru = i[0]
ao = i[1]
aka= i[2]
kaisuu = i[0]/(i[1]+i[2])

answer = divmod(kazoeru, (i[1]+i[2]))

if ao == 0:
    print(0)
    exit()

#商の分を計算
aa = ao * answer[0]

#あまりの分を計算
if answer[1] == 0:
    print(aa)
    exit()

#あまり6で、青が6なら
# あまりが青より多いなら(あまり4、青2)
if answer[1] >= ao:
    aa += ao
#あまりが青より少ないなら(あまり1、青3)
else:
    aa += answer[1]
print(aa)
### BUGGY CODE ###

import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i = 0, max(Cs)+1
    index = (max_i + min_i)//2
    while True:
        if not func(index):
            if func(index+1):
                print(index+1)
                break
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1


### FIXED CODE ###

import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i, index = 0, max(Cs)+1, 1
    while True:
        if func(index):
            index, max_i = (index-1 + min_i)//2, index-1
        else:
            index, min_i = (index+1 + max_i)//2, index+1
        if min_i > max_i:
            print(min_i)
            break
### BUGGY CODE ###

import bisect
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, Q = list(map(int, next(sys.stdin).split()))
STX = [list(map(int, next(sys.stdin).split())) for _ in range(N)]
D = [int(next(sys.stdin)) for _ in range(Q)]


class LinkedNode:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next


ans = [-1 for _ in range(Q)]

last = LinkedNode(value=len(D) - 1)
unfixed = last
while unfixed.value > 0:
    unfixed = LinkedNode(value=unfixed.value - 1, next=unfixed)
# 最後から最初に戻れる
last.next = unfixed

prev = last
node = unfixed
for s, t, x in sorted(STX, key=lambda stx: (stx[2], stx[1])):
    # [lo, hi) に出発した人は x で止まる
    # x の小さい順にソート済みなのでここで確定
    lo = bisect.bisect_left(D, s - x)
    hi = bisect.bisect_left(D, t - x)
    start_value = node.value
    while node.next.value != start_value and lo <= node.value < hi:
        prev = node
        node = node.next
    start_value = node.value
    while node.next.value != start_value and not lo <= node.value < hi:
        prev = node
        node = node.next

    node_exists = True
    while lo <= node.value < hi:
        ans[node.value] = x
        # 確定したので LinkedList から消す
        if node.value != node.next.value:
            prev.next = node.next
            node = node.next
        else:
            # 全部消えた
            node_exists = False
            break
    if not node_exists:
        break

for a in ans:
    print(int(a))


### FIXED CODE ###

import bisect
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, Q = list(map(int, next(sys.stdin).split()))
STX = [list(map(int, next(sys.stdin).split())) for _ in range(N)]
D = [int(next(sys.stdin)) for _ in range(Q)]

ans = [-1 for _ in range(Q)]
nexts = [-1 for _ in range(Q)]

for s, t, x in sorted(STX, key=lambda stx: (stx[2], stx[1])):
    # [lo, hi) に出発した人は x で止まる
    # x の小さい順にソート済みなのでここで確定
    lo = max(0, bisect.bisect_left(D, s - x))
    hi = min(len(D), bisect.bisect_left(D, t - x))

    p = lo
    while p < hi:
        if nexts[p] == -1:
            ans[p] = x
            nexts[p] = hi
            p += 1
        else:
            prev = p
            p = nexts[p]
            nexts[prev] = hi

for a in ans:
    print(int(a))
### BUGGY CODE ###


a,b = map(int,input().split())
def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)
def waru(max_gcd,x):
    if max_gcd%x != 0:
        return max_gcd
    else:
        return waru(max_gcd/i,x)

count = 0
max_gcd = gcd(a,b)

for i in range(2,max_gcd+1):
    if i > max_gcd:
        break
    if max_gcd%i == 0:
        count += 1
        max_gcd = waru(max_gcd,i)
print(count+1)


### FIXED CODE ###


a,b = map(int,input().split())
def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)
def waru(max_gcd,x):
    if max_gcd%x != 0:
        return max_gcd
    else:
        return waru(max_gcd//i,x)

count = 0
max_gcd = gcd(a,b)

for i in range(2,max_gcd+1):
    if i*i > max_gcd:
        break
    if max_gcd%i == 0:
        count += 1
        max_gcd = waru(max_gcd,i)
if max_gcd == 1:
    print(count+1)
else:
    print(count+2)
### BUGGY CODE ###

def main():
    import sys
    s = str(input())
    t = list(input())
    t.append('777')
    n = len(s)
    result = 0
    point = 0
    counter = 0
    i = t.pop(0)
    while i != '777':
        if i in s[point:]:
            x = s[point:].index(i)
            result += x + 1
            point += x + 1
            i = t.pop(0)
            counter = 0
        else:
            result += n - point
            point = 0
            counter += 1
            if counter >= 2:
                print(-1)
                sys.exit()
    print(result)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    s = str(input())
    t = str(input())
    if set(t) <= set(s):
        x = -1
        counter = 0
        for i in t:
            x = s.find(i, x+1)
            if x == -1:
                counter += 1
                x = s.find(i)
        print(x+1+counter*len(s))
    else:
        print(-1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
n=int(input())
s=int(input())

def f(b,n):
  ret=0
  while n:
    ret+=n%b
    n//=b
  return ret

for b in range(2,n+2):
  ss=f(b,n)
  if ss==s:
    print(b)
    break
else:
  print(-1)

### FIXED CODE ###

import sys
n=int(input())
s=int(input())

if n==s:
  print(n+1)
  sys.exit(0)

def f(b,n):
  ret=0
  while n:
    ret+=n%b
    n//=b
  return ret

for b in range(2,int(n**0.5)+1):
#for b in range(2,n+2):
  ss=f(b,n)
  if ss==s:
    print(b)
    sys.exit(0)

#n=pb+q
for p in range(int((n-1)**0.5),0,-1):
  q=s-p
  b=(n-q)//p
  if q<0 or b<=q or b<2 or (n-q)%p!=0:
    continue
    
  #print(b,p,q)
  ss=f(b,n)
  if ss==s:
    print(b)
    sys.exit(0)
    
print(-1)
### BUGGY CODE ###

s = list(input())
n = len(s)
ans = [0] * n
for i in range(n):
    if s[i] == 'R':
        l = s[i:].index('L')
        if l % 2 == 0:
            ans[i + l] += 1
        else:
            ans[i + l - 1] += 1
    else:
        r = s[::-1][n - 1 - i:].index('R')
        if r % 2 == 0:
            ans[i - r] += 1
        else:
            ans[i - r + 1] += 1

print(*ans)

### FIXED CODE ###

s = list(input())
n = len(s)
ans = [0] * n
rs = []
ls = []

for i, c in enumerate(s):
    if c == 'R':
        rs.append(i)
    else:
        ls.append(i)

p = 0
for i, l in enumerate(ls):
    ans[l] += (l - p) // 2
    ans[l - 1] += (l - p) // 2
    if (l - p) % 2 == 1:
        ans[l - 1] += 1
    if l + 1 < n:
        p = l + 1

p = n - 1
rs = rs[::-1]
for i, r in enumerate(rs):
    ans[r] += (p - r) // 2
    ans[r + 1] += (p - r) // 2
    if (p - r) % 2 == 1:
        ans[r + 1] += 1
    if r - 1 >= 0:
        p = r - 1

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

N,Q = map(int,input().split())
s = [0]+list(input())+[0]
t = [0]*(Q)
d = [0]*(Q)
counter = [0]*(N+2)
for i in range(Q):
    t[i],d[i] = input().split()
for i in range(1,N+1):
    counter[i] = 1

for i in range(Q):
    for j in range(1,N+1):
        if (s[j] == t[i]):
            if d[i] == "R":
                counter[j+1] = counter[j+1] + counter[j]
            else:
                counter[j-1] = counter[j-1] + counter[j]
            counter[j] = 0
print(N-counter[0]-counter[N+1])

### FIXED CODE ###

N,Q = map(int,input().split())
s =input()
td = []
lend = 0
rend = N-1

for i in range(Q):
    t,d = map(str,input().split())
    td.append([t,d])
td = td[::-1]
for i,j in td:
    if j == "L" and i == s[lend]:#左端を1つずらす
        lend += 1
    if j == "R" and i == s[rend]:#右端を1つずらす
        rend -= 1  
    if rend < (N-1) and j == "L" and i == s[rend+1]:#1つ前の位置を参照して右に戻す
        rend += 1
    if lend > 0 and j == "R" and i == s[lend-1]:#1つ前の位置を参照して左に戻す
        lend -= 1
    if lend > rend:
        break

print(rend - lend + 1)
### BUGGY CODE ###

x, y, z,  k = map(int, input().split())
a = list(int(x) for x in input().split())
b = list(int(x) for x in input().split())
c = list(int(x) for x in input().split())

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ab_1 = []
for i in range(x):
    for j in range(y):
        ab_1.append(a[i]+b[j])
ab_1.sort(reverse=True)   
key = min([k, x*y*z])
ab_2 = ab_1[:key]

abc = []
for p in ab_2:
    for q in c:
        abc.append(p+q)
abc.sort(reverse=True)
for i in range(key):
    print(abc[i])

### 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)
b.sort(reverse=True)
c.sort(reverse=True)
p = []
for i in a:
    for j in b:
        p.append(i+j)
p.sort(reverse=True)
p = p[:min(3001, x*y*z+1)]
q = []
for j in c:
    for i in p:
        q.append(i+j)
q.sort(reverse=True)
for i in range(k):
    print(q[i])
### BUGGY CODE ###

x=int(input())
li=[2]
p=2
i=0
prime=False
if x==2:
    print(2)
else:
    while p<x or prime==False:
        prime=True
        p+=1
        for i in range(len(li)):
            if p%li[i]==0:
                prime=False
        if prime:
            li.append(p)
   
    print(p)
    


### FIXED CODE ###

x=int(input())
p=x-1
prime=False
if x==2:
    print(2)
else:
    while prime==False:
        p+=1
        prime=True
        
        for i in range(2,p-1):
            if p%i==0:
                prime=False
        
        
   
    print(p)
### BUGGY CODE ###

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

ans = 0
for i in range(N-1):
  x = 0
  for j in range(i, N-1):
    if numbers[j] >= numbers[j + 1]:
      x += 1
      i += 1
      if j == N - 2:
        if x > ans:
          ans = x
    else:
      if x > ans:
        ans = x
      break
      
print(ans)

### FIXED CODE ###

def resolve():
    n = int(input())
    h = list(map(int, input().split()))
    c = 0
    ans = 0
    for i in range(n - 1):
        if h[i + 1] <= h[i]:
            c += 1
            if c > ans:
                ans = c
        else:
            c = 0
    print(ans)
 
 
if __name__ == '__main__':
    resolve()
### BUGGY CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
dp=[0]#足場iまでの最小コスト
for i in range(1,N):
    l=max(0,i-K)
    #m=min([d+abs(H[i]-h) for d,h in zip(dp[l:i],H[l:i])])
    m=min(map(lambda d,h:d+abs(H[i]-h),dp[l:i],H[l:i]))
    dp.append(m)
print(dp[-1])

### FIXED CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
dp=[0]#足場iまでの最小コスト
for i in range(1,N):
    l=max(0,i-K)
    m=min([d+abs(H[i]-h) for d,h in zip(dp[l:i],H[l:i])])
    #m=min(map(lambda d,h:d+abs(H[i]-h),dp[l:i],H[l:i]))
    dp.append(m)
print(dp[-1])
### BUGGY CODE ###

N,H = (int(i) for i in input().split())
a = []
b = [0]
for i in range(N):
    A,B = (int(i) for i in input().split())
    a.append(A)
    b.append(B)
    

count = 0
biga = max(a)
bigb = max(b)
b.sort(reverse = True)
while H > 0:
    if bigb > biga:
        H -= bigb
        b.remove(bigb)
        bigb = b[0]
    else:
        H -= biga
    count += 1

print(count)

### FIXED CODE ###

N,H = (int(i) for i in input().split())
a = []
b = [0]
for i in range(N):
    A,B = (int(i) for i in input().split())
    a.append(A)
    b.append(B)
    

count = 0
biga = max(a)
bigb = max(b)
b.sort(reverse = True)

while H > 0:
    if bigb > biga:
        count += 1
        H -= bigb
        b.remove(bigb)
        bigb = b[0]        
    else:
        count += H//biga
        H -= (H//biga)*(biga)
        if H != 0:
            count += 1
        break
        

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

import numpy as np
from collections import deque

ab = np.array([], int)
n,m = map(int, input().split())

for i in range(m):
    ab = np.append(ab, list(map(int, input().split())), axis=0)

ab = ab.reshape(m,2)

path = [[] for _ in range(n)]


for i in range(m):
    path[ab[i][0]-1].append(ab[i][1])
    path[ab[i][1]-1].append(ab[i][0])
    
d = deque([0])
dis = np.ones(n, int) * -1
dis[0] = 0

while d:
    hop = d.popleft()
    for i in path[hop]:
        if dis[i-1] == -1:
            d.append(i-1)
            dis[i-1] = hop+1
            
if np.count_nonzero(dis)+1 != n:
    print('No')
else:
    print('Yes')
    for i in range(1,len(dis)):
        print(dis[i])

### FIXED CODE ###

from collections import deque

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

path = [[] for _ in range(n)]

for i in range(m):
    a,b = map(int, input().split())
    path[a-1].append(b)
    path[b-1].append(a)
    
d = deque([0])
dis = [-1 for _ in range(n)]
dis[0] = 0

while d:
    hop = d.popleft()
    for i in path[hop]:
        if dis[i-1] == -1:
            d.append(i-1)
            dis[i-1] = hop+1
            
if -1 in dis:
    print('No')
else:
    print('Yes')
    for i in range(1,len(dis)):
        print(dis[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline 
n,q=map(int,input().split())
Graph=[[] for _ in range(n+1)]
ans=[0 for _ in range(n+1)]
seen=[False for _ in range(n+1)]

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

for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

def dfs(v):
    seen[v]=True
    for nv in Graph[v]:
        if seen[nv]:
            continue
        else:
            ans[nv]+=ans[v]
            dfs(nv)

dfs(1)
print(*ans[1:])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
#普通にinputするよりstdin.readlineのほうがはやい
input = sys.stdin.readline 
n,q=map(int,input().split())
Graph=[[] for _ in range(n+1)]
ans=[0 for _ in range(n+1)]


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

for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

def dfs(v,par):
    for nv in Graph[v]:
        if nv==par:
            continue
        else:
            ans[nv]+=ans[v]
            dfs(nv,v)

dfs(1,-1)
print(*ans[1:])
### BUGGY CODE ###

import math
n = int(input())
result = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            result += math.gcd(math.gcd(i + 1, j + 1), k + 1)
print(result)

### FIXED CODE ###

import math
n = int(input())
result = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            result += math.gcd(math.gcd(i + 1, j + 1), k + 1)
print(result)
### BUGGY CODE ###

s = input()[::-1]
length = len(s)
a = [0] * length
d = [0] * length
ans = [0] * 2019

a[0] = int(s[0])
d[0] = a[0]
ans[0] = 1 # dif
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * 10**i % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1

# print(int(sum([ans[i] * (ans[i]-1) for i in range(2019)]) / 2) + ans[0])
print(int(sum([ans[i] * (ans[i]-1) for i in range(2019)]) / 2))

### FIXED CODE ###

#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3

S = input()
size = len(S)
L = [0] * 2019

tmp = int(S[size - 1])  # 最後の文字
L[0] = 1
L[tmp] += 1
tmp_r = 1  # 10のn乗を2019で割った余り(n初期値: 1)

for i in reversed(range(size - 1)):  # 最後の文字の一つ手前からループを回す
    n = int(S[i])  # 対象の文字
    tmp_r = (tmp_r*10) % 2019
    r = (n * tmp_r) % 2019
    tmp = (tmp + r) % 2019
    # print(f"{i}桁目:{tmp}")
    L[tmp] += 1

ans = 0
for i in range(2019):
    tmp = L[i]
    if (tmp > 1):
        ans += tmp * (tmp - 1) // 2


def calc(i):
    if (i == 0):
        return


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

H,W,D=map(int,raw_input().split())
C={}
for i in range(H):
	A=map(int,raw_input().split())
	cnt=1
	for j in A:
		C[j]=(i+1,cnt)
		cnt+=1


Q=input()
for i in range(Q):
	L,R=map(int,raw_input().split())
	ans=0
	for j in range(L,R,D):
		ans+=abs(C[j][0]-C[j+D][0])+abs(C[j][1]-C[j+D][1])
	print ans

### FIXED CODE ###

H,W,D=map(int,raw_input().split())
C={}
for i in range(H):
	A=map(int,raw_input().split())
	cnt=1
	for j in A:
		C[j]=(i+1,cnt)
		cnt+=1

dist=[ 0 for i in range(H*W+1) ]

for i in range(1,H*W+1):
	if i<=D:
		continue
	dist[i]=dist[i-D]+abs(C[i-D][0]-C[i][0])+abs(C[i-D][1]-C[i][1])
	

Q=input()
for i in range(Q):
	L,R=map(int,raw_input().split())
	print dist[R]-dist[L]
### BUGGY CODE ###

N,K = (int(x) for x in input().split())
P = list(int(x) for x in input().split())

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

total = [0] * (N-K+1)

for i in range(N-K+1):
    total[i] = sum(P[:K+i]) - sum(P[:i])

print(max(total))
    



### FIXED CODE ###

N,K = (int(x) for x in input().split())
P = list(int(x) for x in input().split())

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

total1 = 0

for i in range(K):
    total1 += P[i]

ans = total1
total2 = 0

for i in range(N-K):

    total1 += P[K+i]
    total2 += P[i]
    
    if ans < total1 - total2:
        ans = total1 - total2


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

num, poi, ans = [int(x) for x in input().split()]

list01 = [poi for x in range(num)]

for i in range(ans):
  list01 = [x -1 for x in list01]
  j = int(input())
  list01[j -1] += 1
  
for k in list01:
  if k <= 0:
    print("No")
  else:
    print("Yes")


### FIXED CODE ###

num, poi, ans = [int(x) for x in input().split()]

list01 = [poi for x in range(num)]
list02 = [0 for x in range(num)]

for i in range(ans):
  j = int(input())
  list02[j-1] += 1

for i in range(num):
  list02[i] = list02[i] + list01[i] - ans

for k in list02:
  if k <= 0:
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

from collections import deque


def calc_expectation(dice):
    return sum(list(range(1, dice + 1))) / dice


line = input().split(" ")
N, K = int(line[0]), int(line[1])
line = input().split(" ")
p = [int(c) for c in line]

max_E = 0
expectations = deque(maxlen=K)
for _ in range(K):
    expectations.append(0)

for s_idx in range(0, N):
    expectations.popleft()
    dice = p[s_idx]
    e = calc_expectation(dice)
    expectations.append(e)
    E = sum(expectations)
    if E < max_E:
        continue
    else:
        max_E = E

print(max_E)


### FIXED CODE ###

from collections import deque


line = input().split(" ")
N, K = int(line[0]), int(line[1])
line = input().split(" ")
dices = [int(c) for c in line]

max_E = 0
expectations = deque([0] * K, maxlen=K)
e_memo = {}
E = 0
for dice in dices:
    E -= expectations.popleft()
    if e_memo.get(dice) is None:
        e_memo[dice] = sum(range(1, dice + 1)) / dice
    e = e_memo[dice]
    expectations.append(e)
    E += e
    if E < max_E:
        continue
    else:
        max_E = E

print(max_E)
### BUGGY CODE ###

n = int(input())
l = map(int,input().split())
total = 1
for i in l:
    total *= i
if total > 1000000000000000000 :
    total = -1
print(total)

### FIXED CODE ###

n = int(input())
l = map(int, input().split())
total = 1

if __name__ == '__main__':
    for i in l:
        total *= i
        if total > 1000000000000000000:
            total = -1
            break

    if 0 in l :
        total = 0
    print(total)
### BUGGY CODE ###

import itertools
H,W,K = map(int,input().split())
S = []
for i in range(H):
  s= map(int,input())
  S.append(list(s))
l = list(itertools.product([0,1], repeat=H-1))
l = [list(li) for li in l]
for i in range(len(l)):
  l[i] = [j+1 for j in range(len(l[i])) if l[i][j] > 0]
  
S_t = [list(x) for x in zip(*S)]
flag = False  
min_cnt = H*W
for i in range(len(l)):
  cnt = 0
  bh = [0]+[li  for li in l[i] if li > 0]+[H]
  white = [0]*(len(bh)-2+1)
  j = 0
  while j < W:
    if flag == True:
      white = [0]*(len(bh)-2+1)
      cnt += 1
      flag = False
    for k in range(len(bh)-1):
      if white[k] + sum(S_t[j][bh[k]:bh[k+1]]) > K:
        flag = True
        break
      white[k] += sum(S_t[j][bh[k]:bh[k+1]])
    if flag == False:
      j += 1
  min_cnt = min(cnt+len(bh)-2,min_cnt)
  
print(min_cnt)    

### FIXED CODE ###

import itertools
H,W,K = map(int,input().split())
S = []
for i in range(H):
  s= map(int,input())
  S.append(list(s))
l = list(itertools.product([0,1], repeat=H-1))
l = [list(li) for li in l]
for i in range(len(l)):
  l[i] = [j+1 for j in range(len(l[i])) if l[i][j] > 0]
  
S_t = [list(x) for x in zip(*S)]
for i in range(W):
  for j in range(1,H):
    S_t[i][j] += S_t[i][j-1]
flag = False  
min_cnt = H*W
for i in range(len(l)):
  cnt = 0
  bh = [0]+[li  for li in l[i] if li > 0]+[H]
  white = [0]*(len(bh)-2+1)
  j = 0
  while j < W:
    if flag == True:
      white = [0]*(len(bh)-2+1)
      cnt += 1
      flag = False
    for k in range(len(bh)-1):
      if bh[k] == 0:
        su = S_t[j][bh[k+1]-1]
      else:
        su = S_t[j][bh[k+1]-1]-S_t[j][max(0,bh[k]-1)]
      if white[k] + su > K:
        if su > K:
          j = W
          cnt = H*W+1
          flag = False
        else:
          flag = True
        break
      white[k] += su
    if flag == False:
      j += 1
  min_cnt = min(cnt+len(bh)-2,min_cnt)
  
print(min_cnt)
### BUGGY CODE ###

import math

N, M = map(int, input().split())
i = math.floor(M / N)

while i >= 1:
    if M % i == 0:
        break
    i = i - 1

print(i)


### FIXED CODE ###

import math

N, M = map(int,input().split())


def calculate(n, m):
    res = 1
    for i in range(1, int(math.pow(m, 0.5))):
        if m % i != 0:
            continue

        j = m // i

        if i <= m // n:
            res = max(res, i)

        if j <= m // n:
            res = max(res, j)

    print(res)


calculate(N, M)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = ''
t1, t2 = [], []

for i in range(n):
    t1.append(a[i])
    t2.append(a[n-1-i])
    if sorted(t1) == sorted(t2):
        ans += str(i+1) + ' '
print(ans[:-1])



### FIXED CODE ###

from collections import Counter

n = int(input())
a = input().split()
# a = list(map(int, input().split()))
ans = ''
# t1, t2 = [], []
t1, t2 = Counter(), Counter()
for i in range(n):
    t1.update(a[i])
    t2.update(a[n-1-i])
    t3 = t1 & t2
    t1 -= t3
    t2 -= t3
    if t1 == t2:
        ans += str(i+1) + ' '
print(ans[:-1])
### BUGGY CODE ###

def rec(h,w,s):
    res = 0
    for dh,dw in [[1,0],[0,1]]:
        nh,nw = h+dh,w+dw
        if 0 <= nh < H and 0 <= nw < W and C[nh][nw].isdigit():
            res = max(res, rec(nh,nw,s+C[nh][nw]))
    return res if res > 0 else int(s)

while 1:
    W,H = map(int,raw_input().split())
    if W == 0: break
    C = [list(raw_input()) for _ in xrange(H)]
    ans = 0
    for h in xrange(H):
        for w in xrange(W):
           if C[h][w].isdigit():
               if w > 0 and C[h][w-1].isdigit() or h > 0 and C[h-1][w].isdigit(): continue
               ans = max(ans, rec(h,w,C[h][w]))
    print ans

### FIXED CODE ###

while 1:
    W,H = map(int,raw_input().split())
    if W == 0: break
    C = [list(raw_input()) for _ in xrange(H)]
    dp = [[0]*W for _ in xrange(H)]
    ans = 0
    for h in xrange(H):
        for w in xrange(W):
            if C[h][w].isdigit():
                dp[h][w] = max(dp[h][w],int(C[h][w]))
                if w > 0: dp[h][w] = max(dp[h][w],int(str(dp[h][w-1])+C[h][w]))
                if h > 0: dp[h][w] = max(dp[h][w],int(str(dp[h-1][w])+C[h][w]))
    print max(max(i) for i in dp)