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

def main():
    n = int(input())
    s = input()
    ls = []

    for i in range(n)[:-2]:
        for j in range(n)[i + 1:]:
            for k in range(n)[j + 1:]:
                ls.append(s[i] + s[j] + s[k])

    print(len(set(ls)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    s = input()

    c = 0
    l1 = set()
    for i in range(n)[:-2]:
        if s[i] in l1:
            continue
        l1.add(s[i])
        l2 = set()
        for j in range(n)[i + 1:-1]:
            if s[j] in l2:
                continue
            l2.add(s[j])
            c += len(set(list(s[j + 1:])))

    print(c)


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

from collections import deque

n,m=map(int,input().split())
a=list(map(int,input().split()))
a=deque(a)
for i in range(m):
  b,c=map(int,input().split())
  for j in range(b):
    a.append(c)
a=list(a)
#print(a)
a.sort(reverse=1)
a=a[:n]





print(sum(a))
#print(a)

### FIXED CODE ###

from collections import deque

n,m=map(int,input().split())
a=deque(map(int,input().split()))
bc=[list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x: x[1])
bc=bc[::-1]
l=0
for b,c in bc:
  if l>n:
    break
  else:
    d=[c]*b
    a.extend(d)
    l+=b


a=list(a)
#print(a)
a.sort(reverse=1)
a=a[:n]





print(sum(a))
#print(a)
### BUGGY CODE ###

import sys
import bisect
from collections import defaultdict
input = sys.stdin.readline


n, m, q = map(int, input().split())
train = defaultdict(list)
for _ in range(m):
    start, end = map(int, input().split())
    train[start].append(end)

for num in range(n):
    train[num].sort()

for _ in range(q):
    left, right = map(int, input().split())
    count = 0
    for num in range(left, right+1):
        candidate = train[num]
        possible = bisect.bisect_right(candidate, right)
        count += possible
    print(count)


### FIXED CODE ###

import sys
input = sys.stdin.readline


n, m, q = map(int, input().split())
DP = [[0]*n for _ in range(n)]

for i in range(m):
    start, end = map(int, input().split())
    DP[start-1][end-1] += 1

for y in range(n):
    for x in range(y, n-1):
        DP[y][x+1] += DP[y][x]

for x in range(n):
    for y in range(x, 0, -1):
        DP[y-1][x] += DP[y][x]

for i in range(q):
    left, right = map(int, input().split())
    print(DP[left-1][right-1])
### BUGGY CODE ###

H, W, M = map(int, input().split())
h = [0] * (H+1)
w = [0] * (W+1)
l = set()
for i in range(M):
  x, y = map(int, input().split())
  h[x] += 1
  w[y] += 1
  l.add((x, y))
  
a = [i for i, x in enumerate(h) if x == max(h)]
b = [i for i, x in enumerate(w) if x == max(w)]

flag = False
for s in a:
  for t in b:
    if (s, t) not in l:
      flag = True
      break
  if flag:
    break
if flag:
  ans = max(h)+max(w)
else:
  ans = max(h)+max(w)-1
print(ans)


### FIXED CODE ###

H, W, M = map(int, input().split())
h = [0] * (H+1)
w = [0] * (W+1)
l = set()
for i in range(M):
  x, y = map(int, input().split())
  h[x] += 1
  w[y] += 1
  l.add((x, y))
  
c = max(h)
d = max(w)
a = [i for i, x in enumerate(h) if x == c]
b = [i for i, x in enumerate(w) if x == d]

flag = False
for s in a:
  for t in b:
    if (s, t) not in l:
      flag = True
      break
  if flag:
    break
ans = c+d
if not flag:
  ans -= 1
print(ans)
### BUGGY CODE ###

N = int(input())

result = 0
for i in range(N):
    result += i

print(result)


### FIXED CODE ###

N = int(input())

n = N - 1
result = 0

if n != 0:
    result = n * (n+1) // 2

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

dp=[[0]*2019 for _ in range(2)]

p=0
cnt=0
for c in input():
    x=int(c)

    for i in range(2019):
        dp[(p+1)&1][(i*10+x)%2019]=dp[p][i]
    dp[(p+1)&1][x]+=1
    p=(p+1)&1
    cnt+=dp[p][0]

print(cnt)

### FIXED CODE ###

from collections import Counter
S=input()[::-1]

X=[0]
md=2019

for i,s in enumerate(S):
    X.append((X[-1]+int(s)*pow(10,i,md))%md)

C=Counter(X)
ans=0
for v in C.values():
    ans+=v*(v-1)//2

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

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


for i in range(n):
  print(1+a.index(i+1),end=" ")


### FIXED CODE ###

a=int(input())
b=[0]*a
c=list(map(int,input().split()))

for i in range(a):
  b[c[i]-1]+=i+1
print(' '.join(map(str, b)))
### BUGGY CODE ###

I=lambda:map(int,input().split())
n,q=I()
s=[0]
d=s*n
f=s+[1]*n
e=[[]for _ in d]
while~-n:n-=1;a,b=I();e[a-1]+=b-1,;e[b-1]+=a-1,
while q:q-=1;p,x=I();d[p-1]+=x
while s:
 v=s.pop()
 for w in e[v]:d[w]+=d[v]*f[w];s+=[w]*f[w];f[w]=0
print(*d)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def dfs(v):
    for w in e[v]:
        if root[w]>=0:continue
        root[w]=v
        dfs(w)
def dfs2(v):
    for w in e[v]:
        if f[w]:continue
        f[w]=1
        data[w]+=data[v]
        dfs2(w)
input=sys.stdin.readline
n,q=map(int,input().split())
e=[[]for _ in range(n)]
root=[0]+[-1]*(n-1)
data=[0]*n
for _ in range(n-1):
    a,b=map(int,input().split())
    e[a-1]+=b-1,
    e[b-1]+=a-1,
#dfs(0)
for _ in range(q):
    p,x=map(int,input().split())
    data[p-1]+=x
f=[1]+[0]*(n-1)
dfs2(0)
print(*data)
### BUGGY CODE ###

n, t = map(int, input().split())
dish = [list(map(int, input().split())) for _ in range(n)]
dish.sort(key=lambda x: x[0])
dp = [[0 for _ in range(3000)] for _ in range(3000)]
ans = 0

for i in range(n):
    for j in range(t):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        nj = j + dish[i][0]
        if nj < t:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + dish[i][1])
    now = dp[i][t- 1] + dish[i][1]
    ans = max(ans, now)

print(ans)

### FIXED CODE ###

n, t = map(int, input().split())
dish = [list(map(int, input().split())) for _ in range(n)]
dish.sort(key=lambda x: x[0])
dp = [[0 for _ in range(3005)] for _ in range(3005)]

ans = 0
for i in range(n):
    for j in range(t):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        nj = j + dish[i][0]
        if nj < t:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + dish[i][1])
    now = dp[i][t- 1] + dish[i][1]
    ans = max(ans, now)

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

def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines

  h,w = map(int,readline().split())
  a = []
  for i in range(h):
    s = list(map(int,readline().split()))
    a.append(s)
  b = []
  for i in range(h):
    t = list(map(int,readline().split()))
    b.append(t)

  dp = [[set() for _ in range(w)] for _ in range(h)]
  dp[0][0].add(abs(a[0][0]-b[0][0]))

  for i in range(h):
    for j in range(w):
      for k in dp[i][j]:
          if i < h-1:
            c = abs(a[i+1][j]-b[i+1][j])
            if k+c < 5000:
              dp[i+1][j].add(k+c)
            dp[i+1][j].add(abs(k-c))
          if j < w-1:
            d = abs(a[i][j+1]-b[i][j+1])
            if k+d < 5000:
              dp[i][j+1].add(k+d)
            dp[i][j+1].add(abs(k-d))

  print(min(dp[h-1][w-1]))
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines

  h,w = map(int,readline().split())
  a = []
  for i in range(h):
    s = list(map(int,readline().split()))
    a.append(s)
  b = []
  for i in range(h):
    t = list(map(int,readline().split()))
    b.append(t)
  C = [[0]*w for _ in range(h)]
  for i in range(h):
      for j in range(w):
          C[i][j] = abs(a[i][j] - b[i][j])

  dp = [[[0]*6321 for i in range(w)] for _ in range(h)]
  dp[0][0][C[0][0]] = 1

  for i in range(h):
    for j in range(w):
      for k in range(6321):
        if dp[i][j][k]:
          if i < h-1:
            c = C[i+1][j]
            if k+c < 6321:
              dp[i+1][j][k+c] = 1
            dp[i+1][j][abs(k-c)] = 1
          if j < w-1:
            d = C[i][j+1]
            if k+d < 6321:
              dp[i][j+1][k+d] = 1
            dp[i][j+1][abs(k-d)] = 1

  for i in range(6321):
    if dp[h-1][w-1][i]:
      print(i)
      break
      
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
mod=10**9+7
N=int(input())
A=[list(map(int, input().split())) for _ in range(N-1)]
G=[ [] for _ in range(N+1)]
for a,b in A:
  G[a].append(b)
  G[b].append(a)
b=[1]*(N+1)
w=[1]*(N+1)  
def dfs(pre,n):
  for i in G[n]:
    if i==pre:
      continue
    dfs(n,i)
    b[n]*=w[i]
    b[n]%=mod
    w[n]*=b[i]+w[i]
    w[n]%=mod

dfs(0,1)
print((b[1]+w[1])%mod)

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
mod=10**9+7
N=int(input())
G=[[] for _ in range(N+1)]
for _ in range(N-1):
    x,y=map(int, input().split())
    G[x].append(y)
    G[y].append(x)
b=[1]*(N+1)
w=[1]*(N+1)
def dfs(pre,n):
  for i in G[n]:
    if i==pre:
      continue
    dfs(n,i)
    b[n]*=w[i]
    b[n]%=mod
    w[n]*=b[i]+w[i]
    w[n]%=mod

dfs(0,1)
print((b[1]+w[1])%mod)
### BUGGY CODE ###

def cal(n):
    if n==0:return 2
    elif n == 1:return 1
    else: return cal(n-1)+cal(n-2)
a = int(input())
print(cal(a))

### FIXED CODE ###

import numpy as np
a = int(input())
p =[0]*(a+1)
def cal(n):
    if p[n] !=0:return p[n]
    if n==0:res =  2
    elif n == 1:res = 1
    else: res =  cal(n-1)+cal(n-2)
    p[n] = int(res)
    return p[n]
print(int(cal(a)))
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0 for _ in range(N+1)]
MOD = int(1e9) + 7
dp[0] = 1
# DP
if 1 not in a:
    dp[1] = 1
for i in range(2, N+1):
    if i in a:
        continue
    dp[i] = (dp[i-2] + dp[i-1]) % MOD
print(dp[-1])

### FIXED CODE ###

import sys

n, m = map(int, input().split())
aaa = set()
if m != 0:
    for _ in range(m):
        aaa.add(int(input()))
    
    
dp = [0] * (n + 1) # 0 array
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0 # 入ってはいけない段に1が存在した場合は0
MOD = int(1e9) + 7

for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i-2] + dp[i-1]) % MOD # 入ってはいけないところからの遷移の場合0を加算
print(dp[n])
### BUGGY CODE ###

n = int(input())

# alp = ["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"]
#
ans = 0
# array1 = np.zeros().reshape( n,10)


# list1 = []
list_s = []

for i in range(n):
    s = input()
    list_s.append(s)

list_s = list(map(sorted, list_s))



ans = sum(map(lambda y: (sum(map(lambda x: x==list_s[y],list_s)) -1),list(range(n))))
# for i in range(n):
#     ans = ans + sum(map(lambda x: x==list_s[i],list_s)) -1

print(int(ans/2))


### FIXED CODE ###

n = int(input())

ans = 0
ans_dict = {}

for i in range(n):
    s = input()
    s = ''.join(sorted(s))
    if(s in ans_dict):
        ans += ans_dict[s]
        ans_dict[s] += 1
    else:
        ans_dict[s] = 1
        
print(int(ans))
### BUGGY CODE ###

#####segfunc######                                                              
def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=0
n,q=map(int,input().split())
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
c=list(map(int,input().split()))
lr=[]
for i in range(q):
    lr.append(list(map(int,input().split())) + [i])
lr.sort(key=lambda x: x[1])
ans=[0]*q
ll=0
lastc=[-1]*(n+1)
for l,r,ind in lr:
    l-=1
    r-=1
    while ll<=r:
        if lastc[c[ll]]==-1:
            lastc[c[ll]]=ll
            update(ll,1)
        else:
            update(lastc[c[ll]],0)
            lastc[c[ll]]=ll
            update(lastc[c[ll]],1)
        ll+=1
    ans[ind]=query(l,r+1)
for i in ans:
    print(i)

### FIXED CODE ###

import sys
input=sys.stdin.readline
#####segfunc######                                                              
def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=0
n,q=map(int,input().split())
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
c=list(map(int,input().split()))
lr=[]
for i in range(q):
    lr.append(list(map(int,input().split())) + [i])
lr.sort(key=lambda x: x[1])
ans=[0]*q
ll=0
lastc=[-1]*(n+1)
for l,r,ind in lr:
    l-=1
    r-=1
    while ll<=r:
        if lastc[c[ll]]==-1:
            lastc[c[ll]]=ll
            update(ll,1)
        else:
            update(lastc[c[ll]],0)
            lastc[c[ll]]=ll
            update(lastc[c[ll]],1)
        ll+=1
    ans[ind]=query(l,r+1)
for i in ans:
    print(i)
### BUGGY CODE ###

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


def solve(inp):
    S = inp.readline().strip()
    Q = int(inp.readline().strip())
    Queries = [inp.readline().strip() for i in range(Q)]

    r = S
    dir = False
    for Query in Queries:
        if Query == "1":
            dir = not dir
        else:
            (T, F, C) = Query.split(' ')
            if dir == (F == "1"):
                r = r + C
            else:
                r = C + r

    if dir:
        r = "".join(reversed(r))

    return r


def main():
    import sys
    result = solve(sys.stdin)
    if result is not None and result != '':
        print(result)


if __name__ == '__main__':
    main()


### FIXED CODE ###

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


def solve(inp):
    S = inp.readline().strip()
    Q = int(inp.readline().strip())
    Queries = [inp.readline().strip() for i in range(Q)]

    l = []
    r = []
    dir = False
    for Query in Queries:
        if Query == "1":
            dir = not dir
        else:
            (T, F, C) = Query.split(' ')
            if dir == (F == "1"):
                r.append(C)
            else:
                l.append(C)

    if dir:
        return "".join(reversed(r)) + "".join(reversed(S)) + "".join(l)
    else:
        return "".join(reversed(l)) + S + "".join(r)


def main():
    import sys
    result = solve(sys.stdin)
    if result is not None and result != '':
        print(result)


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

N, *A = map(int, open(0).read().split())

MOD = 1000000007

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        ans += (A[i] % MOD) * (A[j] % MOD)
        ans %= MOD
print(ans)

### FIXED CODE ###

from itertools import accumulate

MOD = 10 ** 9 + 7
N, *A = map(int, open(0).read().split())

B = list(accumulate(A)) # cumsum

ans = 0
for i in range(N-1):
    ans += A[i] * (B[-1] - B[i]) % MOD
    ans %= MOD
print(ans)
### BUGGY CODE ###

# 常備セット
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

n,wmax = imap()
wv = np.array([iarr() for i in range(n)])
w,v = wv.T[0], wv.T[1]
#dp = np.zeros((n+1, wmax+1),dtype=np.int64)
dp = [[0 for ww in range(wmax+1)] for i in range(n+1)]

for i in range(n):
    for ww in range(wmax+1):
        dp[i+1][ww] = max(dp[i][ww], dp[i][ww-w[i]]+v[i]) if ww-w[i]>=0 else dp[i][ww]

ans = dp[n][wmax]
print(ans)


### FIXED CODE ###

n,w_lim = map(int,input().split())
dp = [[0 for i in range(w_lim+1)] for i in range(n+1)]

w,v = [],[]
for i in range(n):
    ww,vv = map(int,input().split())
    w.append(ww)
    v.append(vv)

#初期条件
for ww in range(w_lim+1): dp[0][ww] = v[0] if ww>=w[0] else 0

#漸化式
for i in range(n-1):
    for ww in range(w_lim+1):
        dp[i+1][ww] = dp[i][ww] if w[i+1]>ww else max(dp[i][ww], dp[i][ww-w[i+1]]+v[i+1])

ans = dp[n-1][w_lim]
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
stx = [map(int, input().split()) for _ in range(n)]
d = [int(input()) for _ in range(q)]

events = []
for s, t, x in stx:
    events.append((s - x, 1, x))
    events.append((t - x, -1, x))

events.sort()

koujichu = set()

i = 0
for di in d:
    while i < len(events) and events[i][0] <= di:
        if events[i][1] == 1:
            koujichu.add(events[i][2])
        else:
            koujichu.remove(events[i][2])
        i += 1
    if len(koujichu):
        print(min(koujichu))
    else:
        print(-1)


### FIXED CODE ###

import sys
from bisect import bisect_left

input = sys.stdin.readline
n, q = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

stx.sort(key=lambda x: x[2])

ans = [-1] * q
jump = [-1] * q
for s, t, x in stx:
    d_start = bisect_left(d, s - x)
    d_stop = bisect_left(d, t - x, lo=d_start)
    while d_start < d_stop:
        if jump[d_start] == -1:
            ans[d_start] = x
            jump[d_start] = d_stop
            d_start += 1
        else:
            d_start = jump[d_start]

for an in ans:
    print(an)
### BUGGY CODE ###

N=input()
S=[ list(raw_input()) for i in range(N)]

A=0
ans=0
for B in range(N):
	T={}

	for i in range(N):
		for j in range(N):
			T[(i,j)]=S[(i+A)%N][(j+B)%N]

	flag=0
	for i in range(N):
		if flag==-1: break
		for j in range(N):
			if T[ (i,j) ]==T[ (j,i) ]:
				pass
			else:
				flag=-1
				break
	else:
		ans+=1*N


print ans

### FIXED CODE ###

N=input()
S=[ list(raw_input()) for i in range(N)]

A=0
ans=0
for B in range(N):
	flag=0
	for i in range(N):
		if flag==-1: break
		for j in range(N):
			x1=(N+i-A)%N
			y1=(N+j-B)%N

			x2=(N+j-A)%N
			y2=(N+i-B)%N

			#print i,j,x1,y1,x2,y2
			if S[x1][y1]==S[x2][y2]:
				pass
			else:
				flag=-1
				#break
	else:
		ans+=1*N


print ans
### BUGGY CODE ###

import math

X, Y = map(int, input().split())

#initial: (X,Y) = (0,0)

num = 10**9 + 7
sum = 0
#print(num)
for i in range(X+1):# i は1step回数。２stepを行う回数は(X-i)//2(余りあったらbreak)
    if (X-i)% 2 == 0:
        j = (X-i)//2
        #print("i and j is ", i, j)
        if i * 2 + j  == Y:
            #conbination_num1 = (math.factorial(i + j) / math.factorial(i)) % num
            sum += math.factorial(i + j) / (math.factorial(i) * math.factorial(j)) % num  

print(int(sum))




### FIXED CODE ###

import math

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n-i) % mod
        rf = rf * (i+1) % mod
    return nf * pow(rf, mod-2, mod) % mod

if __name__ == "__main__":
    X, Y = map(int, input().split())

    #initial: (X,Y) = (0,0)

    num = 10**9 + 7
    sum = 0
    #print(num)
    for i in range(X+1):# i は1step回数。２stepを行う回数は(X-i)//2(余りあったらbreak)
        if (X-i)% 2 == 0:
            j = (X-i)//2
            #print("i and j is ", i, j)
            if i * 2 + j  == Y:
                #conbination_num1 = (math.factorial(i + j) / math.factorial(i)) % num
                sum += combination(i+j, i, num)  

    print(int(sum))
### BUGGY CODE ###

h,w,k = map(int,input().split())

sl = []
for _ in range(h):
    s = list(input())
    s = [int(i) for i in s]
    sl.append(s)
import itertools
sl_ac = []
for s in sl:
     ac = [0] + list(itertools.accumulate(s))
     sl_ac.append(ac)

anss = float("inf")


from itertools import product
for bits in product([0, 1], repeat=h-1):
    ans = 0
    ans += sum(bits)
    p = 0
    group = [0 for i in range(h)]
    for idx, bit in enumerate(bits):
        group[idx] = p
        p += bit
    group[-1] = p
    sum_group = [0 for i in range(sum(bits) + 1)]
    reset = 0
    flag = "OK"
    for i in range(w):
        for j in range(h):
            sum_group[group[j]] += sl[j][i]
        if max(sum_group) > k:
            if i == 0:
                flag = "NG"
            else:
                ans += 1
                reset = i
                sum_group = [0 for i in range(sum(bits) + 1)]
                for j in range(h):
                    sum_group[group[j]] += sl[j][i]
                if max(sum_group) > k:
                    flag = "NG"

    if flag == "OK":
        anss = min(ans, anss)
print(anss)






### FIXED CODE ###

h,w,k = map(int,input().split())

sl = []
for _ in range(h):
    s = list(input())
    s = [int(i) for i in s]
    sl.append(s)
import itertools
sl_ac = []
for s in sl:
     ac = [0] + list(itertools.accumulate(s))
     sl_ac.append(ac)

anss = float("inf")


from itertools import product
for bits in product([0, 1], repeat=h-1):
    ans = 0
    ans += sum(bits)
    p = 0
    group = [0 for i in range(h)]
    for idx, bit in enumerate(bits):
        group[idx] = p
        p += bit
    group[-1] = p
    sum_group = [0 for i in range(sum(bits) + 1)]
    reset = 0
    flag = "OK"
    for i in range(w):
        for j in range(h):
            sum_group[group[j]] += sl[j][i]
        if max(sum_group) > k:
            if i == 0:
                flag = "NG"
            else:
                ans += 1
                reset = i
                sum_group = [0 for i in range(sum(bits) + 1)]
                for j in range(h):
                    sum_group[group[j]] += sl[j][i]
                if max(sum_group) > k:
                    flag = "NG"

    if flag == "OK":
        anss = min(ans, anss)
print(anss)
### BUGGY CODE ###

N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())

sum_v = sum(v)

dp = [[10**18] * (sum_v + 1) for _ in range(N + 1)]

for i in range(N+1):
    dp[i][0] = 0
    
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
    for j in range(sum_v + 1):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
        if j - v[i] == 0:
            dp[i + 1][j] = min(w[i],dp[i][j])
        if dp[i][j] != 10**18:
            dp[i+1][j+v[i]] = min(dp[i][j+v[i]],dp[i][j]+w[i])
		# 品物(w[i],v[i])を選ばないとき、何も加算しない
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

for i in range(sum_v + 1):
    #print(dp[N][sum_v - i],i)
    if dp[N][sum_v - i] <= W and dp[N][sum_v - i] != 0:
        print(sum_v - i)
        exit()

print(0)


### FIXED CODE ###

N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())

sum_v = sum(v)

dp = [[10**18] * (sum_v + 1) for _ in range(N + 1)]

for i in range(N+1):
    dp[i][0] = 0
    
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
    for j in range(sum_v + 1):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
        if j - v[i] == 0:
            dp[i + 1][j] = min(w[i],dp[i][j])
        if dp[i][j] != 10**18:
            dp[i+1][j+v[i]] = min(dp[i][j+v[i]],dp[i][j]+w[i])
		# 品物(w[i],v[i])を選ばないとき、何も加算しない
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

for i in range(sum_v + 1):
    #print(dp[N][sum_v - i],i)
    if dp[N][sum_v - i] <= W and dp[N][sum_v - i] != 0:
        print(sum_v - i)
        exit()

print(0)