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

from sys import stdin
def main():
  _range, _readline = range, stdin.readline
  h, w = map(int, _readline().split())
  s = [_readline().rstrip() + '#' for _ in _range(h)]
  s.append('#' * (w + 1))
  t = [[-1] * w for _ in _range(h + 1)]
  tstart = [-1] * (w + 1)
  for i in _range(h + 1):
    ystart = -1
    si = s[i]
    ti = t[i]
    for j in _range(w + 1):
      tj = tstart[j]
      if si[j] == '#':
        if ystart != -1:
          n = j - ystart
          for k in _range(ystart, j):
            ti[k] += n
          ystart = -1
        if tj != -1:
          n = i - tj
          for k in _range(tj, i):
            t[k][j] += n
          tstart[j] = -1
      else:
        if ystart == -1:
          ystart = j
        if tj == -1:
          tstart[j] = i
  print(max(map(max, t)))
main()

### FIXED CODE ###

h, w = map(int, input().split())
s = [input() + '#' for _ in range(h)]
s.append('#' * w)

yoko = [[0] * w for _ in range(h)]
for i in range(h):
  if s[i][0] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, w + 1):
    if s[i][j] == '#':
      if start != -1:
        for k in range(start, j):
          yoko[i][k] = j - start
        start = -1
    else:
      if start == -1:
        start = j

tate = [[0] * w for _ in range(h)]
for i in range(w):
  if s[0][i] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, h + 1):
    if s[j][i] == '#':
      if start != -1:
        for k in range(start, j):
          tate[k][i] = j - start
        start = -1
    else:
      if start == -1:
        start = j
result = 0
for i in range(h):
  for j in range(w):
    t = yoko[i][j] + tate[i][j] - 1
    if t > result:
      result = t

print(result)
### BUGGY CODE ###

n = int(input())

a = [int(x) for x in input().split()]

for i in range(1,n):
    a[i] += a[i-1]

a = [0] + a

ans = 0

for i in range(1,n+1):
    for j in range(i):
        if a[i] == a[j]:
            ans += 1

print(ans)

### FIXED CODE ###

from collections import defaultdict

n = int(input())

a = [0] + [int(x) for x in input().split()]

d = defaultdict(int)

tmp = 0

for x in a:
    tmp += x
    d[tmp] += 1

ans = 0

for k,v in d.items():
    if v >= 2:
        ans += v * (v - 1) // 2

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

import sys
n = int(input())
a = [int(input()) for _ in range(n)]

num = a[0]
count = 0

if 2 not in a:
    print(-1)
else:
    while num != 2:
        b = num
        num = a[num - 1]
        count += 1
        if a[num - 1] == b:
            print(-1)
            sys.exit()
    print(count + 1)

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

num = a[0]
count = 1

while num != 2 and count < n:
    count += 1
    num = a[num - 1]

if count < n:
    print(count)
else:
    print(-1)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
H, W, K = map(int, input().split())
B = [[0]*W for _ in [0]*H]

for _ in range(K):
    r, c, v = map(int, input().split())
    B[r-1][c-1] = v

dp = [[[0]*4 for _ in [0]*(W+1)] for _ in [0]*(H+1)]

for i in range(H):
    for j in range(W):
        v = B[i][j]
        if v:
            dp[i+1][j+1][0] = max(dp[i+1][j][0], max(dp[i][j+1]))

            dp[i+1][j+1][1] = max(dp[i+1][j][1],
                                  max(dp[i][j+1])+v, dp[i+1][j][0]+v)

            dp[i+1][j+1][2] = max(dp[i+1][j][2], dp[i+1][j][1]+v)

            dp[i+1][j+1][3] = max(dp[i+1][j][3], dp[i+1][j][2]+v)
        else:
            dp[i+1][j+1][0] = max(dp[i+1][j][0], max(dp[i][j+1]))
            dp[i+1][j+1][1] = dp[i+1][j][1]
            dp[i+1][j+1][2] = dp[i+1][j][2]
            dp[i+1][j+1][3] = dp[i+1][j][3]
print(max(dp[-1][-1]))


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
H, W, K = map(int, input().split())
B = {}

for _ in range(K):
    r, c, v = map(int, input().split())
    B[(r-1,c-1)] = v

dp = [[0]*(W+1) for _ in range(4)]
 
for i in range(H):
    for j in range(W):
        if (i, j) in B:
            v = B[(i, j)]
            dp[0][j+1] = max(dp[0][j], dp[0][j+1], dp[1][j+1], dp[2][j+1], dp[3][j+1])
            dp[1][j+1] = max(dp[1][j], dp[0][j+1]+v)
            dp[2][j+1] = max(dp[2][j], dp[1][j]+v)
            dp[3][j+1] = max(dp[3][j], dp[2][j]+v)
        else:
            dp[0][j+1] = max(dp[0][j], dp[0][j+1], dp[1][j+1], dp[2][j+1], dp[3][j+1])
            dp[1][j+1] = dp[1][j]
            dp[2][j+1] = dp[2][j]
            dp[3][j+1] = dp[3][j]
print(max(dp[i][-1] for i in range(4)))
### BUGGY CODE ###

import numpy as np
N = int(input())
per = np.array([0] + [int(i) for i in input().split()])
res = 0
for i in range(1, N+1):
  flag = True
  
  if per[i] > min(per[1:i+1]): 
    pass
  else: 
    res += 1
print(res)

### FIXED CODE ###

N = int(input())
per = [0] + [int(i) for i in input().split()]
res = 0
min_per = per[1]
for i in range(1, N+1):
  min_per = min(min_per, per[i])
  flag = True
  if per[i] > min_per: 
    pass
  else: 
    res += 1
print(res)
### BUGGY CODE ###

S = input()
Q = int(input())
rev_cnt = 0
for i in range(Q):
    query = [_ for _ in input().split()]
    if len(query) == 1:
        rev_cnt += 1
    else:
        if query[1] == '1':
            if rev_cnt%2 == 0:
                S = query[2] + S
            else:
                S = S + query[2]
        else:
            if rev_cnt%2 == 0:
                S = S + query[2]
            else:
                S = query[2] + S
if rev_cnt % 2 == 0:
    print(S)
else:
    print(S[::-1])


### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())
rev_cnt = 0
for i in range(Q):
    query = [_ for _ in input().split()]
    if len(query) == 1:
        rev_cnt += 1
    else:
        if query[1] == '1':
            if rev_cnt%2 == 0:
                S.appendleft(query[2])
            else:
                S.append(query[2])
        else:
            if rev_cnt%2 == 0:
                S.append(query[2])
            else:
                S.appendleft(query[2])
if rev_cnt % 2 == 0:
    print(''.join(S))
else:
    S.reverse()
    print(''.join(S))
### BUGGY CODE ###

import fractions
from functools import reduce

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

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

gcd_max = 0

for i, _ in enumerate(A):
    gcd_max = max(gcd_max, gcd(A[:i] + A[i+1:]))
    
print(gcd_max)

### FIXED CODE ###

from fractions import gcd
 
N = int(input())
A = list(map(int, input().split()))
 
L = [0] * (N+1)
R = [0] * (N+1)
 
L[0] = 0
R[-1] = 0
 
for i in range(len(A)):
    L[i] = gcd(L[i-1], A[i])
    
for i in reversed(range(len(A))):
    R[i] = gcd(R[i+1], A[i])
    
ans = 0    
 
for i in range(N):
    ans = max(ans, gcd(L[i-1], R[i+1]))
    
print(ans)
### BUGGY CODE ###

import math
#1は入っていない
#素数判定
def primesqrt(x):
    for i in range(1,math.floor(math.sqrt(x))+1):
        if x%i==0 and i!=1:
            return False
        #print(sosu)
    return True

a,b=map(int,input().split())
yaku=[]
for i in range(2,min(a,b)+1):
    if a%i==0 and b%i==0:
        yaku.append(i)

ans=1
for num in yaku:
    if primesqrt(num):
        ans+=1
print(ans)


### FIXED CODE ###

import math
#最大公約数
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
#因数分解
def factorize(x):
    f=[]
    div=2
    while div**2<=x:
        while x%div==0:
            f.append(div)
            x=x//div
        div+=1
    if x>1:
        f.append(x)
    return f

"""def factorize(x):
    ans=1#約数１
    div=2
    while div**2<=x:
        while x%div==0:
            x=x//div
            flag=1
        if flag==1:
            ans+=1
        div+=1
        flag=0
    if x>1:
        ans+=1
    return ans"""

a,b=map(int,input().split())
g=gcd(a,b)
f=factorize(g)
print(len(set(f))+1)
### BUGGY CODE ###

import math

def move(n):
	twonum = n // 2
	com = 0
	for i in range(twonum + 1):
		up = n - i
		com += math.factorial(up) // (math.factorial(up - i) * math.factorial(i))
	return com

N, M = map(int, input().split())
a = []
a.append(0)
for i in range(M):
	a.append(int(input()))
a.append(N+1)

s = 1
for i in range(M+1):
	step = a[i+1] - a[i] - 1
	m = move(step)
	s = s * m % 1000000007
	a[i+1] += 1

print(s)


### FIXED CODE ###

MOD = 1000000007

fact = [0 for i in range(100001)] # fact[i] = i! mod MOD
inv_fact = [0 for i in range(100001)] # inv_fact[i] = i!のmod MODでの逆元
 
# aのn乗をPで割った余りを求めるよ
def mod_pow(a, n, P):
	if n == 0: # aの0乗は1（それはそう）
		return 1
	if n%2 == 0: # aの4乗は（aの2乗）の2乗、みたいなノリ
		x = mod_pow(a, n/2, P)
		return (x*x)%P
	# aの5乗はa×（aの4乗）、みたいなノリ
	return (a*mod_pow(a, n-1, P))%P
 
# nCk mod MODを求める！！
def comb(n, k):
	if n < k:
		return 0
	ans = fact[n]
	ans = (ans * inv_fact[k])%MOD
	ans = (ans * inv_fact[n-k])%MOD
	return ans

def move(n):
	twonum = n // 2
	com = 0
	for i in range(twonum + 1):
		up = n - i
		com += comb(up, i)
	return com

# fact,inv_factを初期化
fact[0] = inv_fact[0] = 1
for i in range(100000):
	# (i+1)!ってi!に(i+1)をかけたものだよね
	fact[i+1] = (fact[i]*(i+1))%MOD
	# (i+1)!の逆元って、i!の逆元に(i+1)の逆元をかけたものだよね
	inv_fact[i+1] = (inv_fact[i]*mod_pow(i+1, MOD-2, MOD))%MOD

N, M = map(int, input().split())
a = []
a.append(0)
for i in range(M):
	a.append(int(input()))
a.append(N+1)

s = 1
for i in range(M+1):
	step = a[i+1] - a[i] - 1
	if step > MOD:
		step = step % MOD
	m = move(step)
	s = (s * m) % MOD
	a[i+1] += 1

print(s)
### BUGGY CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))
    ans = 0

    for i in range(n):
        for j in range(n):
            if i == j:
                continue

            if A[i] % A[j] == 0:
                break
        else:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort()
    D = [True] * (10**6 + 1)
    ans = 0

    for i, a in enumerate(A):
        if not D[a]:
            continue
        if (i < n-1 and a != A[i+1]) or i == n-1:
            ans += 1

        j = a
        while (j < 10**6 + 1):
            D[j] = False
            j += a

    print(ans)


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

from itertools import accumulate
mod = 10 ** 9 + 7


def GCD(x, y):
    if y == 0:
        return x
    return GCD(y, x % y)


def LCM(a, b, mod=10 ** 9 + 7):
    res = a * pow(GCD(a, b), mod - 2, mod)
    res %= mod
    res *= b
    res %= mod
    return res


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


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    A_lcm = list(accumulate(A, func=lcm))[-1]

    ans = 0
    for a in A:
        b = A_lcm * pow(a, mod - 2, mod) % mod
        ans = (ans + b) % mod
    print(ans)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

d = defaultdict(int)


def prime_factorization(n):  # 素因数分解
    res = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            res.append((i, cnt))
    if n > 1:
        res.append((n, 1))
    return res


for a in A:
    for i in range(2, int(a ** 0.5) + 1):
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                cnt += 1
                a //= i
            d[i] = max(d[i], cnt)
    if a != 1:
        d[a] = max(d[a], 1)

ans = 0
lcm = 1
for k, v in d.items():
    lcm *= pow(k, v, mod)
    lcm %= mod

for a in A:
    if a == 1:
        ans += lcm
        continue
    l = lcm*pow(a, mod-2, mod)
    ans += l
    ans %= mod

print(ans % mod)
### BUGGY CODE ###

N = int(input())
S = [0] + list(input())
Q = int(input())

Query = [list(input().split()) for i in range(Q)]

for i in range(Q):
    if Query[i][0] == '1':
        S[int(Query[i][1])] = Query[i][2]
    else:
        s = set([])
        for j in range(int(Query[i][1]),int(Query[i][2])+1):
            s.add(S[j])
        print(len(s))

### FIXED CODE ###

import sys
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
S = [set([a]) for a in LS2()]


def seg_func(x,y):
    return x | y

unit = set([])

class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self,N,seg_func,unit):
        self.N = N
        self.func = seg_func
        self.unit = unit
        self.tree = [self.unit]*(2*self.N)
    def build(self,init_value):  # 初期値を[N,2N)に格納
        for i in range(self.N):
            self.tree[i+self.N] = init_value[i]
        for i in range(self.N-1,0,-1):
            self.tree[i] = self.func(self.tree[i << 1],self.tree[i << 1 | 1])
    def set_val(self,i,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i << 1],self.tree[i << 1 | 1])
    def fold(self,L,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        vL = self.unit
        vR = self.unit
        while L < R:
            if L & 1:
                vL = self.func(vL,self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.func(self.tree[R],vR)
            L >>= 1
            R >>= 1
        return self.func(vL,vR)


seg = SegTree(N,seg_func,unit)
seg.build(S)

Q = I()
for i in range(Q):
    a,b,c = LS()
    if a == '1':
        b = int(b)-1
        seg.set_val(b,set([c]))
    else:
        b,c = int(b)-1,int(c)-1
        print(len(seg.fold(b,c+1)))
### BUGGY CODE ###

n,m = map(int,input().split())
alis = list(map(int,input().split()))
lis = [list(map(int,input().split())) for x in range(m)]
clis = [[x[1]]*x[0] for x in lis]
clis=(sum(clis,[]))
clis.sort(reverse=True)
alis.sort()
num = 0
ans_lis=[]
for x,y in zip(alis,clis):
    if x>=y:
        ans_lis.append(x)
    else:
        ans_lis.append(y)
    num += 1
if num < len(alis):
    ans__ = sum(alis[num:])
    print(sum(ans_lis,ans__))
else:
    print(sum(ans_lis))


### FIXED CODE ###

n,m = map(int,input().split())
alis = list(map(int,input().split()))
lis = [list(map(int,input().split())) for x in range(m)]
for x in alis:
    lis.append([1,x])
lis.sort(reverse=True,key=lambda x:x[1])
ans = 0
for x in lis:
    (number,point) = x
    if number >= n:
        number = n
        ans += number * point
        #print(n)
        #print(ans,'+=',number,'*',point)
        break
    ans += number * point
    n -= number
    #print(n)
    #print(ans,'+=',number,'*',point)
print(ans)
#print(lis)
### BUGGY CODE ###

import itertools
n = int(input())
a = list(map(int, input().split()))
amaria = []
ans = 0
p = 10 ** 9+7
#for i in itertools.combinations(a,2):
    #ans += i[0]* i[1]
    #print(ans)
for i in range(n):
    amaria.append(a[i]%p)
for j in itertools.combinations(amaria,2):
    ans += j[0]* j[1]
print(ans % p)

### FIXED CODE ###

import itertools
n = int(input())
a = list(map(int, input().split()))
suma = sum(a)-a[0]
ans = 0
p = 10 ** 9+7
for i in range(len(a)-1):
    ans += a[i]*suma
    suma -= a[i+1]
    ans = ans%p
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
print(min([S[:i].count('W') + S[i+1:].count('E') for i in range(N)]))


### FIXED CODE ###

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

def f(S):
  count = {'W': 0, 'E': 0}
  yield count['W'], count['E']
  for c in S:
    count[c] += 1
    yield count['W'], count['E']

count = list(f(S))
print(min([count[i-1][0] + count[-1][1] - count[i][1] for i in range(1, N+1)]))
### BUGGY CODE ###

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

for i in range(1,n+1):
    print(a.count(i))



### FIXED CODE ###

import collections
 
n = int(input())
a = list(map(int, input().split()))
ac = collections.Counter(a)
 
for i in range(1,n+1):
    print(ac[i])
### BUGGY CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n,ma,mb=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(n)]
dp=[[float('inf')]*500000 for i in range(n+1)]
dp[0][0]=0
for i in range(n):
    for j in range(500000):
        if dp[i][j]!=float('inf'):
            a=j//1000
            b=j%1000
            dp[i+1][(a+abc[i][0])*1000+b+abc[i][1]]=min(dp[i][j]+abc[i][2],dp[i+1][(a+abc[i][0])*1000+b+abc[i][1]])
            dp[i+1][j]=min(dp[i+1][j],dp[i][j])
ans=float('inf')
now=[ma,mb]
while 1:
    a,b=now
    ans=min(ans,dp[n][a*1000+b])
    if a+ma>400 or b>400:
        break
    now=[a+ma,b+mb]
if ans==float('inf'):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n,ma,mb=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(n)]
dp=[[[float('inf')]*(400+1) for i in range(400+1)] for j in range(n+1)]
dp[0][0][0]=0
for i in range(n):
    a,b,c=abc[i]
    for j in range(400):
        for k in range(400):
            if dp[i][j][k]!=float('inf'):
                dp[i+1][j+a][k+b]=min(dp[i+1][j+a][k+b],dp[i][j][k]+c)
                dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k])
ans=float('inf')
now=[ma,mb]
while 1:
    a,b=now
    ans=min(ans,dp[n][a][b])
    if a+ma>400 or b+mb>400:
        break
    now=[a+ma,b+mb]
if ans==float('inf'):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

#C
N = int(input())
pair = [1]
s = ''.join(sorted(input()))
s_set = {s}
s_list = [s]
for i in range(1, N):
    s = ''.join(sorted(input()))
    if s in s_set:
        pair[s_list.index(s)] += 1        
    else:
        s_list.append(s)
        s_set.add(s)
        pair.append(1)
result = 0
for i in pair:
    result += (i * (i-1))//2
print(result)

### FIXED CODE ###

#C
N = int(input())
pairdic = {}
s = ''.join(sorted(input()))
pairdic[s] = 1
for i in range(1, N):
    s = ''.join(sorted(input()))
    if s in pairdic:
        pairdic[s] += 1        
    else:
        pairdic[s] = 1
result = 0
for i in pairdic:
    result += (pairdic[i] * (pairdic[i]-1))//2
print(result)
### BUGGY CODE ###

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

array = []
for s in set(S):
    array.append(S.count(s))

len_array = len(array)

def recall(cur,t=1,total=0):
    if cur==len_array:
        return t
    for i in [array[cur],1]:
        total += recall(cur+1,t*i)
    return total

print((recall(0)-1)%(10**9+7))

### FIXED CODE ###

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

mod = 10**9 + 7
alphabet = [chr(i) for i in range(97,97+26)]

ans = 1
for letter in alphabet:
    ans *= S.count(letter) + 1
    ans =  ans%mod
ans -= 1

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

def main():
    import sys
    sys.setrecursionlimit(10**8)
    input=sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    num1,num2,num3=0,0,0
    for i in range(n):
        if a[i]==1:
            num1+=1
        elif a[i]==2:
            num2+=1
        else:
            num3+=1
    dp=[[[0]*(n+1) for i in range(n+1)] for j in range(n+1)]
    flag=[[[0]*(n+1) for i in range(n+1)] for j in range(n+1)]
    def f(n1,n2,n3):
        if flag[n1][n2][n3]:
            return dp[n1][n2][n3]
        if n1==n2==n3==0:
            return 0
        flag[n1][n2][n3]=1
        ret=1/(1-(n-n1-n2-n3)/n)
        if n1>0:
            ret+=f(n1-1,n2,n3)*(n1/n)/(1-(n-n1-n2-n3)/n)
        if n2>0:
            ret+=f(n1+1,n2-1,n3)*(n2/n)/(1-(n-n1-n2-n3)/n)
        if n3>0:
            ret+=f(n1,n2+1,n3-1)*(n3/n)/(1-(n-n1-n2-n3)/n)
        dp[n1][n2][n3]=ret
        return dp[n1][n2][n3]
    print(f(num1,num2,num3))
if __name__=="__main__":
    main()

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[-1.0 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if dp[n1][n2][n3]>=0.0:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0.0
    ret=n
    if n1>0:
        ret+=f(n1-1,n2,n3)*n1
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*n2
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*n3
    ret*=1.0/(n1+n2+n3)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
maze = [input()for _ in range(H)]


def bfs(startx: int, starty: int) -> set:
    dxdy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    queue = deque()
    queue.appendleft((startx, starty, 0))
    reached = set()
    while queue:
        d = queue.pop()
        if d[0] == W - 1 and d[1] == H - 1:
            return d[2]
        for a in dxdy:
            x = d[0] + a[0]
            y = d[1] + a[1]
            if (x, y) not in reached and 0 <= x < W and 0 <= y < H and maze[y][x] != '#':
                queue.appendleft((x, y, d[2] + 1))
                reached.add(d[:2])
    return -1


d = bfs(0, 0)
if d == -1:
    print(-1)
    exit()
cnt = 0
for c in maze:
    cnt += c.count('#')
print(H * W - cnt - d - 1)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
maze = [input()for _ in range(H)]


def bfs(startx: int, starty: int) -> set:
    dxdy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    queue = deque()
    queue.appendleft((startx, starty, 0))
    reached = set()
    while queue:
        d = queue.pop()
        if d[0] == W - 1 and d[1] == H - 1:
            return d[2]
        for a in dxdy:
            x = d[0] + a[0]
            y = d[1] + a[1]
            if (x, y) not in reached and 0 <= x < W and 0 <= y < H and maze[y][x] != '#':
                reached.add((x, y))
                queue.appendleft((x, y, d[2] + 1))
    return -1


d = bfs(0, 0)
if d == -1:
    print(-1)
    exit()
cnt = 0
for c in maze:
    cnt += c.count('#')
print(H * W - cnt - d - 1)
### BUGGY CODE ###

H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
cum = [[0]*W for _ in range(H+1)]
for j in range(W):
  for i in range(1,H+1):
    cum[i][j] = cum[i-1][j]+S[i-1][j]
    
cum = np.array(cum)
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  p = deque()
  judge = False
  for a in range(len(q)-1):
    x = cum[q[a+1]]-cum[q[a]]
    if (x>K).any():
      judge = True
      break
    else:
      p.append(x)

  if judge:
    continue
  
  t_a = len(q)-2
  l = [0]*len(p)
  for w in range(W):
    for x,a in enumerate(p):
      l[x]+=a[w]
      if l[x]>K:
        t_a+=1
        l = [0]*len(p)
        for z,b in enumerate(p):
          l[z] = b[w]
        break
  ans = min(ans,t_a)
    
print(ans)

### FIXED CODE ###

def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    j = 0
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    t_a = len(q)-2
    if t_a>=ans:
      continue
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if (x>K).any():
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    n = len(p)
    l = [0]*n
    for w in range(W):
      y = [l[j]+p[j][w] for j in range(n)]
      if max(y)>K:
        t_a+=1
        l = [p[j][w] for j in range(n)]
        if t_a>=ans:
          judge = True
          break
      else:
        l = y
    if judge:
      continue
    ans = min(ans,t_a)

  print(ans)
  
main()