Harryxun/stf_run huggingface dataset:
N=int(input())
if N%2 == 0:
    print(round(N/2*(N-1)))
else:
    print(round((N-1)/2*N)))

### FIXED CODE ###

N=int(input())
 
print(int(N*(N-1)//2))
while True:
H,W = (int(x) for x in input().split())
if H == 0 and W == 0:
    break

    i = 0
    while i < H:
        j = 0
        while j < W:
            print ("#", end='')
            j += 1
        print ('')
        i += 1


### FIXED CODE ###

while True:
    H,W = (int(x) for x in input().split())
    
    if H == 0 and W == 0:
        break
    
    i = 0 
    while i < H:
        j = 0 
        while j < W:
            print ("#", end='')
            j += 1
        print ('')
        i += 1
    print ('')
import sys

sys.setrecursionlimit(100000)

def calc_state_number(stair_num, now_stair, damaged_step_list, memo):
    # print(str(now_stair) + '/' + str(stair_num))
    if memo[now_stair-1] != -1:
        return memo[now_stair-1]
    if now_stair in damaged_step_list:
        memo[now_stair-1] = 0
        return memo[now_stair-1]
    if now_stair > stair_num:
        memo[now_stair-1] = 0
        return memo[now_stair-1]
    if now_stair == stair_num:
        memo[now_stair-1] = 1
        return memo[now_stair-1]
    memo[now_stair-1] = (calc_state_number(stair_num, now_stair+1, damaged_step_list, memo) + calc_state_number(stair_num, now_stair+2, damaged_step_list, memo))%1000000007
    return memo[now_stair-1]

if __name__ == '__main__':
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    a = sorted(a)

    memo = [-1] * (N*2)

    answer = 1
    if a[-1::] == N:
        answer = 0

    for i in range(1, M):
        if a[i-1] + 1 == a[i]:
            answer = 0

    if answer != 0:
        answer = calc_state_number(N, 0, a, memo)

    print(answer)


### FIXED CODE ###

if __name__ == '__main__':
   n, m = map(int,input().split())
   a = set([int(input()) for i in range(m)])

   MOD = 1000000007

   dp = [0 for i in range(n+1)]
   dp[0] = 1
   if 1 in a:
      dp[1] = 0
   else:
      dp[1] = 1

   for i in range(2,n+1):
      if (i-1 in a) and (i-2 in a):
         dp[i] = 0
      elif i-1 in a:
         dp[i] = dp[i-2] % MOD
      elif i-2 in a:
         dp[i] = dp[i-1] % MOD
      else:
         dp[i] = (dp[i-1] + dp[i-2]) % MOD

   print(dp[n])
d=set()
for i in[0]*int(input()):d^={input()}
print(len(p))

### FIXED CODE ###

d={}
for _ in[0]*int(input()):
 i=input()
 d[i]=d.get(i,0)^1
print(sum(d.values()))
import sys
from collections import Counter

def defs(c1, c2):
    if c1[0][0] > c2[0][0]:
        return c1[1], c2[0]
    else:
        return c1[0], c2[1]

def main():
    input = sys.stdin.readline
    
    n = int(input())
    m = [int(i) for i in input().split()]
    
    even = [m[i] for i, _ in enumerate(m) if i % 2 == 0]
    odd = [m[i] for i, _ in enumerate(m) if i % 2 == 1]
    
    even_c = Counter(even).most_common()
    odd_c = Counter(odd).most_common()
    
    if even_c[0] == odd_c[0]:
        print(len(m) / 2)
        return
    
#    print(even_c)
#    print(odd_c)
    
    even_c, odd_c = defs(even_c, odd_c)
    
    if even_c[1] == odd_c[1]:
        ans = len(odd) - min(even_c[1], odd_c[1])
        
    else:
        ans = len(m) - (even_c[1] + odd_c[1])
    
    print(ans)


if __name__ == '__main__':
    main()
    


### FIXED CODE ###

import sys
from collections import Counter
 
def main():
    input = sys.stdin.readline
    
    n = int(input())
    m = [int(i) for i in input().split()]
    
    #偶数列 奇数列
    even = [m[i] for i, _ in enumerate(m) if i % 2 == 0]
    odd = [m[i] for i, _ in enumerate(m) if i % 2 == 1]
    
    #頻値を取り出す
    even_c = Counter(even).most_common()
    odd_c = Counter(odd).most_common()
    
    ans = -1
    
    #print(even_c)
    #print(odd_c)
    #print(len(even_c))
    
    #最頻値の比較
    if even_c[0][0] != odd_c[0][0]:
        ans = len(m) - (even_c[0][1] + odd_c[0][1])
    
    #偶数列と奇数列の最頻値の数字が同じかつ、全て同じ数字じゃない
    elif even_c[0][0] == odd_c[0][0] and len(even_c) > 1:
        ans1 = len(m) - (even_c[0][1] + odd_c[1][1])
        ans2 = len(m) - (even_c[1][1] + odd_c[0][1])
        ans = ans1 if ans1 <= ans2 else ans2
    
    #全て同じ
    else:
        ans = even_c[0][1]
        
    #出力
    print(ans)
    
if __name__ == '__main__':
    main()
import math


def f(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append(i)

    if temp != 1:
        arr.append(temp)

    if arr == []:
        arr.append(n)

    return arr


def main():
    # return
    # N = int(input())
    # N,= [int(a) for a in input().split()]
    A, B = [int(a) for a in input().split()]

    gcd = math.gcd(A, B)

    if gcd == 1:
        print(1)
    else:
        print(len(f(gcd)) + 1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import math


def gcdf(a, b):
    if a > b:
        a, b = b, a
    if b%a==0:
        return a
    return gcdf(a, b % a)


def f(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append(i)

    if temp != 1:
        arr.append(temp)

    if arr == []:
        arr.append(n)

    return arr


def main():
    # return
    # N = int(input())
    # N,= [int(a) for a in input().split()]
    A, B = [int(a) for a in input().split()]

    gcd = gcdf(A, B)

    if gcd == 1:
        print(1)
    else:
        print(len(f(gcd)) + 1)


if __name__ == "__main__":
    main()
N = int(input())
A = list(map(int, input().split()))

print(max(A)-min(A))



### FIXED CODE ###

N = int(input())

if N % 2 == 0:
    print(N)
else :
    print(N * 2)
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([i,xy[0]])
    b.append([i,xy[1]])

a.sort(key=lambda x: x[1])
b.sort(key=lambda x: x[2])
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for i in range(len(a)-1):
    adj[a[i][0]].append([a[i+1][1]-a[i][1], a[i+1][0]])
    adj[a[i+1][0]].append([a[i+1][1]-a[i][1], a[i][0]])
for i in range(len(b)-1):
    adj[b[i][0]].append([b[i+1][1]-b[i][1], b[i+1][0]])
    adj[b[i+1][0]].append([b[i+1][1]-b[i][1], b[i][0]])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    current = heapq.heappop(h)
    if visited[current[1]] != True and current[0] < d[current[1]]:
        d[current[1]] = current[0]
        visited[current[1]] = True
        cnt += 1
        if cnt == n:
            break
        for edge in adj[current[1]]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(sum(d))
        


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq
import sys
input = sys.stdin.readline

n = int(input())
a = [[] for _ in range(n)]
b = [[] for _ in range(n)]
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a[i]=[xy[0],i]
    b[i]=[xy[1],i]

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
#d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
totalcost = 0 
while h:
    cost, node = heapq.heappop(h)
    #if visited[node] != True and cost < d[node]:
    if visited[node] != True:        
        #d[node] = cost
        visited[node] = True
        totalcost += cost
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]]:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(totalcost)
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]

import bisect


N, H = mi()
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = mi()

B = sorted(B)
a = max(A)
m = bisect.bisect_left(B, a)
'''
s = 1
e = N
m = (s+e)//2
pre_m = 0
while True:
    m = (s+e)//2
    if B[m-1] > a:
        e = m
    elif B[m-1] <= a:
        s = m
    if s==e:
        m -= 1
        break
    #else:
        #break
    if e-s==1 and pre_m==m:
        break
    pre_m = m
'''
rem = H - sum(B[m:])
if rem >= 0:
    print((N-m)+rem//a+(rem%a==0))
else:
    for i in range(m, N):
        rem += B[i]
        if rem>=0:
            print(N-i)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

S = input()
print(S[:3] + '8' + S[4:])
X,Y=map(int(input(),split())
x,y=map(int(input(),split())
a=(X-x)*(Y-y)
print(a)

### FIXED CODE ###

X,Y=map(int,input().split())
x,y=map(int,input().split())
a=(X-x)*(Y-y)
print(a)
import math

A ,B ,H ,M =map(int,input().split())

dighour:float = 360*((H+M/60)/12)
digmin:float =  360*(M/60)
length:float = 0

deg = abs(dighour-digmin)

length = A**2 + B**2 - 2 * A * B math.cos(math.radians(deg))

'''
if dighour > digmin and abs(dighour - digmin) <= 180:
    length = math.sqrt((A **2 + B **2) - ((2*A*B) * math.cos(math.radians(abs(dighour-digmin)))))
elif dighour > digmin and abs(dighour - digmin) > 180:
    length = math.sqrt((A **2 + B **2) - ((2*A*B) * math.cos(math.radians(360 - abs(dighour-digmin)))))
elif dighour < digmin and abs(digmin - dighour) <= 180:
    length = math.sqrt((A **2 + B **2) - ((2*A*B) * math.cos(math.radians((abs(digmin-dighour))))))
elif dighour < digmin and abs(digmin - dighour) > 180:
    length = math.sqrt((A **2 + B **2) - ((2*A*B) * math.cos(math.radians((360 - abs(digmin-dighour))))))
'''

print(length)

### FIXED CODE ###

import math

A ,B ,H ,M =map(int,input().split())

dighour:float = 30*H + M*0.5
digmin:float =  M * 6
length:float = 0

deg = abs(dighour-digmin)
length = math.sqrt(A**2 + B**2 - (2 * A * B * math.cos(math.radians(deg))))

'''
if dighour > digmin and abs(dighour - digmin) <= 180:
    length = math.sqrt((A **2 + B **2) - ((2*A*B) * math.cos(math.radians(abs(dighour-digmin)))))
elif dighour > digmin and abs(dighour - digmin) > 180:
    length = math.sqrt((A **2 + B **2) - ((2*A*B) * math.cos(math.radians(360 - abs(dighour-digmin)))))
elif dighour < digmin and abs(digmin - dighour) <= 180:
    length = math.sqrt((A **2 + B **2) - ((2*A*B) * math.cos(math.radians((abs(digmin-dighour))))))
elif dighour < digmin and abs(digmin - dighour) > 180:
    length = math.sqrt((A **2 + B **2) - ((2*A*B) * math.cos(math.radians((360 - abs(digmin-dighour))))))
'''

print(length)
def main():

    TaroScore = HanaScore = 0
    n = int(input())
    for _ in range(n):
        [Taro, Hana] = list(input().lower().split())

        lenT = len(Taro)
        lenH = len(Hana)

        if Taro == Hana:
            TaroScore += 1
            HanaScore += 1
        
        else:
            for _ in range(min(lenT, lenH)+1):
                if Taro == '' or ord(Taro[0]) < ord(Hana[0]):
                    HanaScore += 3
                    break
                elif Hana == '' or ord(Taro[0]) > ord(Hana[0]):
                    TaroScore += 3
                    break
                else:
                    Taro = Taro[1:]
                    Hana = Hana[1:]

    print(TaroScore, HanaScore)

if __name__ == '__main__':
    main()



### FIXED CODE ###

score_t = score_h = 0
n = int(input())
for _ in range(n):
    animal_t, animal_h = input().split()
    if animal_t == animal_h:
        score_t += 1
        score_h += 1
    elif animal_t > animal_h:
        score_t += 3
    else:
        score_h += 3

print(score_t, score_h)
K, N = int(input())
A = list(map(int, input().split()))
m = K + A[0] - A[N-1]
for i in range(N-1):
  d = A[i+1] - A[i]
  m = max([d, m])
print(K-m)

### FIXED CODE ###

K, N = map(int, input().split())
A = list(map(int, input().split()))
m = K + A[0] - A[N-1]
for i in range(N-1):
  d = A[i+1] - A[i]
  m = max([d, m])
print(K-m)
n = int(input())
if n % 7 == 0 or n % 4 == 0:
   print("Yes")
elif (n % 28) % 4 == 0 or (n % 28) % 7 == 0:
   print("Yes")
else:
   print("No")

### FIXED CODE ###

n,k = map(int, input().split())
if n%k == 0:
    print("0")
else: 
       print("1")
import sys

sys.setrecursionlimit(200000)

n,q = (int(num) for num in input().split())
neighbor = [[] for _ in range(n)]
visited = [0] * n
val = [0] * n
ab = []
for i in range(n-1):
    a,b = (int(num)-1 for num in input().split())
    ab.append((a,b))

    
for item in ab:
    a = item[0]
    b = item[1]
    neighbor[a].append(b)
    neighbor[b].append(a)
    
        
#print(par)
#print(neighbor)
#print(rank)

for _ in range(q):
    p,x = (int(num) for num in input().split())
    p -= 1
    val[p] += x
    
que = [0]
visited[0] = 1
last = 0
while que != []: 
    idx = que.pop(0)
    val[idx] += last
    last = val[idx]
    for i in neighbor[idx]:
        if visited[i] == 0:
            visited[i] = 1
            que.append(i)
            
for num in val:
    ans += str(num) + " "
print(ans)




### FIXED CODE ###

n,q = (int(num) for num in input().split())
par = [n] * n
visited = [0] * n
val = [0] * n
ab = []
for i in range(n-1):
    a,b = (int(num)-1 for num in input().split())
    par[b] = a
    
for _ in range(q):
    p,x = (int(num) for num in input().split())
    p -= 1
    val[p] += x

for i in range(1,n):
    val[i] += val[par[i]]
    
ans = ""
for num in val:
    ans += str(num) + " "
print(ans)
N = int(input())
A = list(map(int, input().split()))

j = True
for i in range(N):
    if A[i] % 2 == 0:
        if A[i] %3 == 0 or A[i] % 5 ==0:
            pass
        else:
            j = False
            exit()
            
if j == Ture:
    print("APPROVED")
else:
    print("DENIED") 

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
j = True
for i in range(N):
    if A[i] % 2 == 0:
        if A[i] %3 == 0 or A[i] % 5 ==0:
            pass
        else:
            j = False
            
if j == True:
    print("APPROVED")
else:
    print("DENIED")
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()))

ab=[]
for i in range(x):
    for j in range(y):
        ab.append(a[i]+b[j])
ab.sort()
aa=[]
for i in range(k):
    if x*y-i>=0:
        aa.append(ab[x*y-i])
ans=[]
for i in range(len(aa)):
    for j in range(z):
        ans.append(aa[i]+c[j])
ans.sort()
for i in range(k):
    print(ans[len(ans)-i-1]
        

### FIXED CODE ###

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

ab=[]
for i in range(x):
    for j in range(y):
        ab.append(a[i]+b[j])
ab.sort()
aa=[]
for i in range(k):
    if x*y-i-1>=0:
        aa.append(ab[x*y-i-1])
ans=[]
for i in range(len(aa)):
    for j in range(z):
        ans.append(aa[i]+c[j])
ans.sort()
for i in range(k):
    print(ans[len(ans)-i-1])
import networkx as nx

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

S = [list(input()) for _ in range(n)]
G = nx.DiGraph()

start = (n, n)
cnt = 0
goal = (n, n + 1)

for i in range(n):
    for j in range(n):
        if S[i][j] != "#":
            if S[i][j] == "o":
                cnt += 1
                G.add_edge(start, (i, j), capacity=1)
            if i + 1 < n:
                if S[i + 1][j] != "#":
                    G.add_edge((i, j), (i + 1, j), weight=-1)
            if j + 1 < n:
                if S[i][j + 1] != "#":
                    G.add_edge((i, j), (i, j + 1), weight=-1)
            G.add_edge((i, j), goal, capacity=1)
# G.add_node(start, demand=cnt)
# G.add_node(goal, demand=-cnt)
mincostflow = nx.max_flow_min_cost(G, start, goal)
ans = nx.cost_of_flow(G, mincostflow)
print(-ans)


### FIXED CODE ###

import networkx as nx

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

S = [list(input()) for _ in range(n)]
G = nx.DiGraph()

start = (n, m)
cnt = 0
goal = (n, m + 1)

for i in range(n):
    for j in range(m):
        if S[i][j] != "#":
            if S[i][j] == "o":
                cnt += 1
                G.add_edge(start, (i, j), capacity=1)
            if i + 1 < n:
                if S[i + 1][j] != "#":
                    G.add_edge((i, j), (i + 1, j), weight=-1)
            if j + 1 < m:
                if S[i][j + 1] != "#":
                    G.add_edge((i, j), (i, j + 1), weight=-1)
            G.add_edge((i, j), goal, capacity=1)
# G.add_node(start, demand=cnt)
# G.add_node(goal, demand=-cnt)
mincostflow = nx.max_flow_min_cost(G, start, goal)
ans = nx.cost_of_flow(G, mincostflow)
print(abs(ans))
alpha = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
C = []
b = ""
while True:
    a = input()
    a = a.lower()
    b += a
    if a == 'END_OF_TEXT':
        break
for i in range(len(alpha)):
    k = b.count(alpha[i])
    C.append(k)
for i in range(len(alpha)):
    print(alpha[i]+" :",C[i])


### FIXED CODE ###

import sys
alpha = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
C = []
b = ""
for line in sys.stdin:
    a = line.lower()
    b += a
for i in range(len(alpha)):
    k = b.count(alpha[i])
    C.append(k)
for i in range(len(alpha)):
    print(alpha[i]+" :",C[i])
c = [list(map(int, input().split())) for _ in range(3)]

a = [0] * 3
b = [0] * 3
ans = "Yes"
a[0] = 0
b[0] = c[0][0] - a1
b[1] = c[0][1] - a1
b[2] = c[0][2] - a1
a[1] = c[1][0] - b[0]
a[2] = c[2][0] - b[0]
for i in range(3):
    for j in range(3):
        if a[i] + b[j] != c[i][j]:
            ans = "No"

print(ans)


### FIXED CODE ###

c = [list(map(int, input().split())) for _ in range(3)]

a = [0] * 3
b = [0] * 3
ans = "Yes"
for a1 in range(101):
    a[0] = a1
    b[0] = c[0][0] - a1
    b[1] = c[0][1] - a1
    b[2] = c[0][2] - a1
    a[1] = c[1][0] - b[0]
    a[2] = c[2][0] - b[0]
    for i in range(3):
        for j in range(3):
            if a[i] + b[j] != c[i][j]:
                ans = "No"

print(ans)
import itertools

T = list(input())
location_q = []
Tstr = []
count_D_PD = []

for s in range(len(T)):
    if T[s] == '?':
        location_q.append(s)

for i in itertools.product(['P','D'], repeat=3):
    for j in range(len(location_q)):
        T[location_q[j]] = i[j]
    Tstr.append(''.join(T))
# print(Tstr)

for k in range(len(Tstr)):
    count_D_PD.append(Tstr[k].count('D') + Tstr[k].count('PD'))
# print(count_D_PD)
# print(max(count_D_PD))
# print(count_D_PD.index(max(count_D_PD)))
print(Tstr[count_D_PD.index(max(count_D_PD))])


### FIXED CODE ###

T = list(input())
for i in range(len(T)):
    if T[i] == '?':
        T[i] = 'D'

print(''.join(T))
a = int(input())
b = int(input())
c = int(input())


if a < b:
    d = b
    another = a
else:
    d = a
    another = b

if d < c:
    d2 = str(d)
    d = str(c)

f = d + d2

print(int(f)+another)

### FIXED CODE ###

s = input()

num = list(s)

num.sort()
num.reverse()

print(int(num[0] + num[1]) + int(num[2]))
IN = iter(Input.split('\n')).__next__
def input():
    return IN()

# 入力
h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s_ = [int(i) for i in input()]
    s.append(s_)
ans = float("INF")
for i in range(2**(h-1)):
    d = [(i >> j) & 1 for j in range(h-1)]
    count, count_tmp = [0]*(sum(d)+1), [0]*(sum(d)+1)
    ans_, res = 0, 0
    flag = False
    for w_ in range(w):
        count[0] += s[0][w_]
        count_tmp[0] += s[0][w_]
        res += 1
        tmp = 0
        for h_ in range(1, h):
            if d[h_-1]: tmp += 1
            if s[h_][w_]:
                count[tmp] += 1
                count_tmp[tmp] += 1
        for j in count:
            if j > k:
                if res==1:
                    flag = True
                    break
                else:
                    for idx in range(sum(d)+1):
                        count[idx] = count_tmp[idx]
                    ans_ += 1
                    res = 0
                    break
        if flag: break
        count_tmp = [0]*(sum(d)+1)
    ans_ += sum(d)
    ans = min(ans, ans_)
print(ans)

### FIXED CODE ###

h, w, k = map(int, input().split())
s = [[int(i) for i in input()] for _ in range(h)]
ans = (h-1)+(w-1)
for i in range(2**(h-1)):
    d = [(i >> j) & 1 for j in range(h-1)]
    count, count_tmp = [0]*(sum(d)+1), [0]*(sum(d)+1)
    ans_, res = 0, 0
    flag = False
    for w_ in range(w):
        count[0] += s[0][w_]
        count_tmp[0] += s[0][w_]
        res += 1
        tmp = 0
        for h_ in range(1, h):
            if d[h_-1]: tmp += 1
            if s[h_][w_]:
                count[tmp] += 1
                count_tmp[tmp] += 1
        for j in count:
            if j > k:
                if res==1:
                    flag = True
                    break
                else:
                    for idx in range(sum(d)+1):
                        count[idx] = count_tmp[idx]
                    ans_ += 1
                    res = 1
                    break
        if flag: break
        count_tmp = [0]*(sum(d)+1)
    if flag: continue
    ans_ += sum(d)
    ans = min(ans, ans_)
print(ans)