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

import heapq

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

root1 = {}
root2 = {}
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[(u, v)] = a
    root2[(u, v)] = b

def edge(root, x):
    return([(b, root[(a, b)]) for (a, b) in root if a == x] + [(a, root[(a, b)]) for (a, b) in root if b == x])

root1 = [edge(root1, i + 1) for i in range(n)]
root2 = [edge(root2, i + 1) for i in range(n)]

def min_cost(root, start):
    S = [[0, start]]
    heapq.heapify(S)
    D = [float("inf")] * n
    D[start - 1] = 0
    while len(S) > 0:
        cost, site = heapq.heappop(S)
        if D[site - 1] > cost:
            D[site - 1] = cost
        for (site2, cost2) in root[site - 1]:
            if D[site2 - 1] > cost + cost2:
                heapq.heappush(S, [cost + cost2, site2])
    return D

jpy = min_cost(root1, s)
snuke = min_cost(root2, t)
cost = [jpy[i] + snuke[i] for i in range(n)]

for i in range(n):
    print(10 ** 15 - min(cost[i:]))

### FIXED CODE ###

import heapq

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

root1 = []
for i in range(n):
    root1.append({})
root2 = []
for i in range(n):
    root2.append({})
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[u - 1][v] = a
    root1[v - 1][u] = a
    root2[u - 1][v] = b
    root2[v - 1][u] = b

def min_cost(root, start): # 経路の端点を１つ指定して任意の点への最小コストを計算
    S = [[0, start]]
    heapq.heapify(S)
    D = [float("inf")] * n
    D[start - 1] = 0
    while len(S) > 0:
        cost, site = heapq.heappop(S)
        if D[site - 1] < cost:
            continue
        for site2, cost2 in root[site - 1].items():
            if D[site2 - 1] > cost + cost2:
                D[site2 - 1] = cost + cost2
                heapq.heappush(S, [cost + cost2, site2])
    return D

jpy = min_cost(root1, s) # 円で両替地点まで移動する最小コスト
snuke = min_cost(root2, t) # 両替地点からスヌークで移動する最小コスト
cost = [jpy[i] + snuke[i] for i in range(n)] # 両替地点についてループ

minimum_cost = []
temp_min = cost[n - 1]
for i in reversed(range(n)):
    temp_min = min(temp_min, cost[i])
    minimum_cost.append(temp_min)

for i in reversed(range(n)):
    print(10 ** 15 - minimum_cost[i])
### BUGGY CODE ###

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

### FIXED CODE ###

from math import gcd
K = int(input())
ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            ans += gcd(gcd(i, j), k)
print(ans)
### BUGGY CODE ###

# d
N,K = map(int, input().split())
xy = []
for _ in range(N):
    xy.append( tuple(map(int, input().split())) )
xs,ys = map(list, zip(*xy))
xs.sort()
ys.sort()
ans = float('inf')
for l in range(N):
    for r in range(l+1,N):
        for b in range(N):
            for t in range(b+1,N):
                xl,xr = xs[l],xs[r]
                yb,yt = ys[b],ys[t]
                cnt = 0
                for xi,yi in xy:
                    if xl<=xi<=xr and yb<=yi<=yt: 
                        cnt += 1
                if cnt>=K:
                    ans = min(ans, (xr-xl)*(yt-yb))
print(ans)

### FIXED CODE ###

# d
N,K = map(int, input().split())
xy = []
for _ in range(N):
    xy.append( tuple(map(int, input().split())) )
xs,ys = map(list, zip(*xy))
xs.sort()
ys.sort()
ans = float('inf')
for l in range(N):
    for r in range(l+1,N):
        for b in range(N):
            for t in range(b+1,N):
                xl,xr = xs[l],xs[r]
                yb,yt = ys[b],ys[t]
                cnt = 0
                for xi,yi in xy:
                    if xl<=xi<=xr and yb<=yi<=yt: 
                        cnt += 1
                if cnt>=K:
                    ans = min(ans, (xr-xl)*(yt-yb))
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

# import time
# s = time.time()

MOD = 10 ** 9 + 7

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

dp = [[0] * (1 << (N)) for _ in range(N + 1)]

dp[0][0] = 1
# for tmp in dp:
#     print (tmp)

for i in range(N):
    for j in range(N):
        if A[i][j] == 0: #仲良くない時
            continue
        #以下仲が良い時のみの処理
        for k in range(1 << N):
            if (1 << j) & k == 0: #まだペアになっていない女の人の時
                dp[i + 1][k + (1 << j)] = (dp[i + 1][k + (1 << j)] + dp[i][k]) % MOD
        # print (dp[i + 1])

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

# f = time.time()

# print (f - s, '秒')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7

N = int(input())

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

dp = [-1] * (1 << N)
dp[(1 << N) - 1] = 1

def dfs(group, count):
    if dp[group] != -1:
        return dp[group]
    res = 0
    for i in range(N):
        if (group >> i) & 1 == 0 and A[count][i] == 1:
            res += dfs(group + (1 << i), count + 1)
    dp[group] = res % MOD
    return dp[group]

tmp = dfs(0, 0)

print (tmp)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, *a = map(int, read().split())

    r = 0
    for i1 in range(n):
        r += min(a[:i1+1]) >= a[i1]

    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

r = 0
x = 200001
for num in P:
  if x >= num:
    r += 1
    x = num
print(r)
### BUGGY CODE ###

M = int(input())
A=list(map(int,input().split()))
A.sort()
k=0
judge=0
ans=0
while True:
    if k>=len(A)-1:
        break
    for i in range(len(A)-1,k,-1):
        judge=0
        if A[i]%A[k]==0:
            if A[i]==A[k]:
                judge=1
            A.pop(i)
    k+=1
    ans=ans+judge

print(len(A)-ans)

### FIXED CODE ###

M = int(input())
A=list(map(int,input().split()))
A.sort()
ma=A[-1]
is_prime = [True] * (ma + 1)
for i in A:
    if not is_prime[i]:
        continue
    for j in range(i * 2, ma + 1, i):
        is_prime[j] = False
k=[i for i in range(ma + 1) if is_prime[i]]
N=[]
if len(A)==1:
    print(1)
else:
    if A[0] !=A[1]:
        N.append(A[0])
    for i in range(1,len(A)-1):
        if A[i-1]!=A[i] and A[i]!=A[i+1]:
            N.append(A[i])
    if A[len(A)-2] != A[len(A)-1]:
        N.append(A[len(A)-1])
    s=set(k) & set(N)
    print(len(s))
### BUGGY CODE ###

def main():
  import sys
  from heapq import heappush, heappop
  input = sys.stdin.readline
  
  N,D,A = map(int,input().split())
  hq = []
  for i in range(N):
    x,h = map(int,input().split())
    heappush(hq, (x,0,h))

  ans = 0
  b = 0
  while(len(hq) > 0):
    x,a,h = heappop(hq)
    if a == 0:
      if b < h:
        cnt = ((h-b)+A-1)//A
        ans += cnt
        b += A*cnt
        heappush(hq, (x+2*D,1,A*cnt))
    else:
      b -= h
  
  print(ans)

if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
  import sys
  from heapq import heappush, heappop, heapify
  input = sys.stdin.readline
  
  N,D,A = map(int,input().split())
  hq = []
  for i in range(N):
    x,h = map(int,input().split())
    hq.append((x,0,h))
  heapify(hq)

  ans = 0
  b = 0
  while(len(hq) > 0):
    x,a,h = heappop(hq)
    if a == 0:
      if b < h:
        cnt = ((h-b)+A-1)//A
        ans += cnt
        b += A*cnt
        heappush(hq, (x+2*D,1,A*cnt))
    else:
      b -= h
  
  print(ans)

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-

N = int(input())
A_list = list(map(int, input().split()))
ans = 0

for i in range(N):
    if i != N -1:
        for j in range(i+1, N):
            ans += A_list[i] * A_list[j]
while ans >= 10 ** 11 + 700:
    ans -= 10 ** 11 + 700
while ans >= 10 ** 9 + 7:
    ans -= 10 ** 9 + 7
print(ans)


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

N = int(input())
A_list = list(map(int, input().split()))
ans = 0
SUM = sum(A_list)
for i in range(N):
    SUM -= A_list[i]
    if i != N -1:
        ans += A_list[i] * SUM
while ans >= 10 ** 21 + 7000000000000:
    ans -= 10 ** 21 + 7000000000000
while ans >= 10 ** 19 + 70000000000:
    ans -= 10 ** 19 + 70000000000
while ans >= 10 ** 17 + 700000000:
    ans -= 10 ** 17 + 700000000
while ans >= 10 ** 15 + 7000000:
    ans -= 10 ** 15 + 7000000
while ans >= 10 ** 13 + 70000:
    ans -= 10 ** 13 + 70000
while ans >= 10 ** 11 + 700:
    ans -= 10 ** 11 + 700
while ans >= 10 ** 9 + 7:
    ans -= 10 ** 9 + 7
print(ans)
### BUGGY CODE ###

import sys
n = int(sys.stdin.readline())
a = [int(sys.stdin.readline()) for i in range(n)]
a = [-1] + a

def cond(a):
    if 2 not in a:
        return -1

    visited = []
    current = 1
    count = 0

    while True:
        if current == 2:
            return count
        if current in visited:
            return -1
        count += 1
        visited.append(current)
        current = a[current]

print(cond(a))


### FIXED CODE ###

import sys
n = int(sys.stdin.readline())
a = [int(sys.stdin.readline()) for i in range(n)]
a = [-1] + a

def cond(a):
    if 2 not in a:
        return -1

    visited = set()
    current = 1
    count = 0

    while True:
        if current == 2:
            return count
        if current in visited:
            return -1
        count += 1
        visited.update((current,))
        current = a[current]

print(cond(a))
### BUGGY CODE ###

n = input()
s = input()

n = int(n)

ans = []
counts = 0

for i in range(n - 2):
    for j in range(i + 1, n - 1):

        if s[i] + s[j] in ans:
            continue
        else:
            counts += len(set(s[j + 1: n]))
            ans.append(s[i] + s[j])

        # for k in range(j + 1, n):
        #     ans.append(s[i] + s[j] + s[k])

# ans = list(set(ans))
print(counts)

### FIXED CODE ###

n = input()
s = str(input())
n = int(n)

ans_count =0

for i in range(10):
    for j in range(10):
        for k in range(10):
            i_pos = s.find(str(i))

            if i_pos < 0:
                continue

            j_pos = s.find(str(j),i_pos+1)

            if j_pos < 0:
                continue

            k_pos = s.find(str(k), j_pos +1)

            if k_pos < 0:
                continue

            ans_count += 1

print(ans_count)
### BUGGY CODE ###

import fractions

def coprime2(a, b):
    return fractions.gcd(a, b) == 1

A,B = map(int, input().split())
num_set = set()
i=2
while True:
    if(A%i==0 and B%i==0):
        num_set.add(i)
        A = A//i
        B = B//i
        if(coprime2(A,B)==1):
            break
    else:
        i = i+1
print(len(num_set)+1)

### FIXED CODE ###

def prime_factor(n):
    ass = set()
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.add(i)
            n = n//i
    if n != 1:
        ass.add(n)
    return ass

A,B = map(int, input().split())
num_set = set()

A_set = prime_factor(A)
B_set = prime_factor(B)

num_set = A_set.intersection(B_set)

#while True:
#    if(A%i==0 and B%i==0):
#        num_set.add(i)
#        A = A//i
#        B = B//i
#        if(coprime2(A,B)==1):
#            break
#    else:
#        i = i+1
print(len(num_set)+1)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

H, W = map(int,input().split())
sth, stw = 0, 0
glh, glw = H-1, W-1

INF = 10000
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (0,1)}

from collections import deque

def bfs(init):

    next_q = deque([])
    if Gmap[init[0]][init[1]]=="#":
        Dist[init[0]][init[1]] = 1
        next_q.append([0,0,"#"])
    else:
        Dist[init[0]][init[1]] = 0
        next_q.append([0,0,"."])

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, fg = next_q.popleft()
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            fgs = Gmap[hs][ws]
            if fgs=='#' and fg == '.':
                Dist[hs][ws] = min(Dist[h][w]+1, Dist[hs][ws])
            else:
                Dist[hs][ws] = min(Dist[h][w], Dist[hs][ws])
            next_q.append([hs,ws,fgs])
    return Dist

def main():
    ret = bfs([sth,stw])
    print(ret[glh][glw])

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    H, W = map(int,input().split())
    sth, stw = 0, 0
    glh, glw = H-1, W-1

    INF = 10000
    Gmap = [list(input()) for _ in range(H)]
    Dist = [[INF]*W for _ in range(H)]
    direc = {(1,0), (0,1)}

    if Gmap[0][0]=='#':
        Dist[0][0]=1
    else:
        Dist[0][0]=0

    for h in range(H):
        for w in range(W):
            nw = Gmap[h][w]
            for d in direc:
                hs, ws = h + d[0], w + d[1]
                if 0<=hs<H and 0<=ws<W:
                    cr = Gmap[hs][ws]
                    Dist[hs][ws] = min(Dist[hs][ws], Dist[h][w] + (cr=='#' and nw=='.'))
    print(Dist[glh][glw])

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

N = int(input())
A = list(map(int, input().split(' ')))
rect_long = 0
rect_small = 0
while A != []:
    long_max = max(A)
    if A.count(long_max) >= 2:
        rect_long += long_max
        A.remove(long_max)
        A.remove(long_max)
        break
    A.remove(long_max)

while A != []:
    small_max = max(A)
    if A.count(small_max) >= 2:
        rect_small += small_max
        break
    A.remove(small_max)

print(rect_long * rect_small)

### FIXED CODE ###

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

a = sorted(a, reverse=True)

count = 0
edge = []

i = 0
for _ in range(n-1):
    if a[i] == a[i+1]:
        count = count + 1
        edge.append(a[i])
        i = i + 1
        if count == 2:
            break
    i = i + 1

s = edge[0]*edge[1] if count == 2 else 0
print(s)
### BUGGY CODE ###

n,s = map(int,input().split())
maxx = s // 10000
maxy = s // 5000 
isloop = True
for x in range(maxx+1):
    if(isloop==False):
        break
    for y in range(maxy+1):
        if(isloop==False):
            break
        z = (s-10000*x-5000*y)//1000
        if((x+z+y)==n and z >= 0):
            print(x,y,z)
            isloop=False
            break

if(isloop==True):
    print(-1,-1,-1)

### FIXED CODE ###

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

isloop = True
for x in range(2001):
    
    if(isloop==False):
        break
    xv = x*10000
    for y in range(2001):
        
        if(isloop==False):
            break
        yv = y*5000
        xysum = xv+yv
        if(xysum > s):
            continue
        
        z = (s-(xysum))//1000
        if((x+z+y)==n):
            print(x,y,z)
            isloop=False
            break

if(isloop==True):
    print(-1,-1,-1)
### BUGGY CODE ###

def main():
    import math
    import sys
    input = sys.stdin.readline

    n,k = map(int,input().split())
    a = sorted(list(map(int,input().split())))
    f = sorted(list(map(int,input().split())),reverse=True)
    check = []
    for i in range(n):
        check.append((a[i]*f[i],a[i],f[i]))

    def search(x):
        count = 0

        for i,j,k in check:
            if i > x:
                y = math.floor(x/k)
                count += j-y
        return count

    left = -1
    right = 10**12+2
    while right > left+1:
        mid = (right+left)//2
        if search(mid) > k:
            left = mid
        else:
            right = mid
    print(right)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import math
    import sys
    input = sys.stdin.readline

    n,k = map(int,input().split())
    a = sorted(list(map(int,input().split())))
    f = sorted(list(map(int,input().split())),reverse=True)
    check = []
    for i in range(n):
        check.append((a[i]*f[i],a[i],f[i]))

    def search(x):
        count = 0

        for i,j,k in check:
            if i > x:
                y = math.floor(x/k)
                count += j-y
        return count

    left = -1
    right = 10**12+2
    while right > left+1:
        mid = (right+left)//2
        if search(mid) > k:
            left = mid
        else:
            right = mid
    print(right)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import itertools
n = int(input())
l = list(map(int,input().split()))
l = sorted(l)
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        #print(l[i],l[j])
        for z in range(j+1,n):
            if l[i]+l[j]>l[z]:
                cnt  += 1
                #print(l[i],l[j],l[z])
print(cnt)

### FIXED CODE ###

from bisect import bisect_left
n = int(input())
l = list(map(int,input().split()))
l = sorted(l)
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        #print(l[i],l[j])
        cnt += bisect_left(l, l[i] + l[j]) - (j + 1)
print(cnt)
### BUGGY CODE ###

N = int(input())
li =  [ int(it) -1 for it in input().split() ] 

import sys
sys.setrecursionlimit(10000000)

from functools import lru_cache
MOD = 1000000007
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
@lru_cache(maxsize=None)
def modinv(a):
    (inv, q, gcd_val) = egcd(a, MOD)
    return inv % MOD
@lru_cache(maxsize=None)
def factorial(k):
  if (k<=1):
    return 1
  return (factorial(k-1)*k)%MOD
@lru_cache(maxsize=None)
def combination(n,m):
  return (factorial(n)*modinv(factorial(m))*modinv(factorial(n-m)))%MOD

#print ( factorial(5),factorial(3) )
#print ( combination(5,3) )

import collections as col
c = col.Counter( li ).items()
a = [ it for it in c if it[1] == 2][0][0]
p1 = li.index(a)
p2 = li[p1+1:].index(a) + 1 + p1
#print ( p1 , p2 )
H = p1 + (N-p2)
#print ( H )

li=[]
for i in range(1,N+2):
  a =  (combination(N+1,i) - (combination(H,i-1)if (i-1)<=H else 0))%MOD
  li.append(a)
print ( "\n".join( map(str,li) ) )
  

### FIXED CODE ###

N = int(input())
li =  [ int(it) -1 for it in input().split() ] 

import sys
sys.setrecursionlimit(10000000)

from functools import lru_cache
MOD = 1000000007
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
@lru_cache(maxsize=None)
def modinv(a):
    (inv, q, gcd_val) = egcd(a, MOD)
    return inv % MOD

fac_li = [0]*( 1000009 )
if True:
  s = 1
  for i in range(1,1000001):
    s = (s*i)%MOD
    fac_li[i] = s
def factorial(k):
  if (k<=1):
    return 1
  return fac_li[k]
@lru_cache(maxsize=None)
def combination(n,m):
  return (factorial(n)*modinv(factorial(m))*modinv(factorial(n-m)))%MOD

#print ( factorial(5),factorial(3) )
#print ( combination(5,3) )

import collections as col
c = col.Counter( li ).items()
a = [ it for it in c if it[1] == 2][0][0]
p1 = li.index(a)
p2 = li[p1+1:].index(a) + 1 + p1
#print ( p1 , p2 )
H = p1 + (N-p2)
#print ( H )

li=[]
for i in range(1,N+2):
  a =  (combination(N+1,i) - (combination(H,i-1)if (i-1)<=H else 0))%MOD
  li.append(a)
print ( "\n".join( map(str,li) ) )
### BUGGY CODE ###

def calc(a_list, b_list, x):
    inf = 10**11
    aa = [a - x for a in a_list]
    bb = [b - x for b in b_list]
    if len([b for b in bb if b>=0])*len([a for a in aa if a>=0]) >0:
        p_1 = max([b for b in bb if b>=0][0], [a for a in aa if a>=0][0])
    else:
        p_1 = inf
    if len([b for b in bb if b<=0])*len([a for a in aa if a<=0]) >0:
        p_2 = max(abs(max([b for b in bb if b<=0])), abs(max([a for a in aa if a<=0])))
    else:
        p_2 = inf
    if len([b for b in bb if b<=0])*len([a for a in aa if a>=0]) >0:
        b_tmp = max([b for b in bb if b<=0])
        a_tmp = min([a for a in aa if a>=0])
        p_3 = a_tmp - b_tmp + min(abs(a_tmp), abs(b_tmp))
    else:
        p_3 = inf
    if len([b for b in bb if b>=0])*len([a for a in aa if a<=0]) >0:
        b_tmp = min([b for b in bb if b>=0])
        a_tmp = max([a for a in aa if a<=0])
        p_4 = b_tmp - a_tmp + min(abs(a_tmp), abs(b_tmp))
    else:
        p_4 = inf
    return min(p_1, p_2, p_3, p_4)

a,b,q = map(int, input().split())
a_list = []
b_list = []
q_list = []
for i in range(a):
    a_list.append(int(input()))
for j in range(b):
    b_list.append(int(input()))
a_list = sorted(a_list)
b_list = sorted(b_list)
for k in range(q):
    q = int(input())
    ans = calc(a_list, b_list, q)
    print(ans)

### FIXED CODE ###

import bisect
a, b, q = map(int, input().split())
s = []
for i in range(a):
    s.append(int(input()))
t = []
for j in range(b):
    t.append(int(input()))
inf = 10 ** 18
s = [-inf] + s + [inf]
t = [-inf] + t + [inf]
for k in range(q):
    x = int(input())
    s_r, t_r = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = inf
    for s_ in [s[s_r], s[s_r - 1]]:
        for t_ in [t[t_r], t[t_r - 1]]:
            d = min(abs(x-s_), abs(x-t_)) + abs(s_ - t_)
            res = min(d, res)
    print(res)
### BUGGY CODE ###

from itertools import combinations, chain

H, W, K = map(int, input().split())
Sss = []
for _ in range(H):
    Sss.append(list(map(int, input())))


def h_divide(Sss, div_is):
    result = []
    for s, e in zip(chain([0], div_is), chain(div_is, [len(Sss)])):
        result.append(Sss[s:e])
    return result


def _v_end(Sss, start, K):
    count = 0
    for i in range(start, len(Sss[0])):
        s = sum(map(lambda Ss: Ss[i], Sss))
        if count + s > K:
            return i - 1
        count += s
    return len(Sss[0]) - 1


def v_end(Ssss, start, K):
    result = -1
    for Sss in Ssss:
        end = _v_end(Sss, start, K)
        if end < start:
            return -1
        if result < 0 or result > end:
            result = end
    return result


def v_div_count(Ssss, K):
    start, result = 0, 0
    while True:
        end = v_end(Ssss, start, K)
        if end < 0:
            return -1
        if end == len(Ssss[0][0]) - 1:
            break
        result += 1
        start = end + 1
    return result


h_cands = list(range(1, len(Sss)))
ans = -1
for n in range(len(h_cands) + 1):
    for comb in combinations(h_cands, n):
        Ssss = h_divide(Sss, list(comb))
        cnt = v_div_count(Ssss, K)
        if cnt < 0:
            continue
        if ans < 0 or ans > n + cnt:
            ans = n + cnt
print(ans)


### FIXED CODE ###

from itertools import combinations, chain

H, W, K = map(int, input().split())
Sss = []
for _ in range(H):
    Sss.append(list(map(int, input())))


def h_divide(Sss, div_is):
    result = []
    for s, e in zip(chain([0], div_is), chain(div_is, [len(Sss)])):
        result.append(Sss[s:e])
    return result


def _v_end(Sss, start, K):
    count = 0
    for i in range(start, len(Sss[0])):
        s = sum(map(lambda Ss: Ss[i], Sss))
        if count + s > K:
            return i - 1
        count += s
    return len(Sss[0]) - 1


def v_end(Ssss, start, K):
    result = -1
    for Sss in Ssss:
        end = _v_end(Sss, start, K)
        if end < start:
            return -1
        if result < 0 or result > end:
            result = end
    return result


def v_div_count(Ssss, K):
    start, result = 0, 0
    while True:
        end = v_end(Ssss, start, K)
        if end < 0:
            return -1
        if end == len(Ssss[0][0]) - 1:
            break
        result += 1
        start = end + 1
    return result


h_cands = list(range(1, len(Sss)))
ans = -1
for n in range(len(h_cands) + 1):
    for comb in combinations(h_cands, n):
        if ans > 0 and n >= ans:
            continue
        Ssss = h_divide(Sss, list(comb))
        cnt = v_div_count(Ssss, K)
        if cnt < 0:
            continue
        if ans < 0 or ans > n + cnt:
            ans = n + cnt
print(ans)