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

import sys
import itertools
from operator import itemgetter #sortedの対象を決めたい
from fractions import gcd #最大公約数
from math import ceil, floor, sqrt, isinf #小数点切り上げ、切り捨て、平方根
from copy import deepcopy #参照で影響されないコピー
from collections import Counter, deque #要素ごとの出現回数、双方向アクセス可能データ型
import heapq
import numpy as np
from functools import reduce
sys.setrecursionlimit(200000)

input = sys.stdin.readline
# template


def main():
    n, k = map(int, input().split())
    h = [int(i) for i in input().split()]

    dp = [0] * n

    for i in range(1, n):
        L = [dp[j] + abs(h[i] - h[j]) for j in range(max(0, i-k), i)]
        dp[i] = min(L)

    print(dp[-1])

if __name__ == "__main__":
    main()



### FIXED CODE ###

import sys
import itertools
from operator import itemgetter #sortedの対象を決めたい
from fractions import gcd #最大公約数
from math import ceil, floor, sqrt, isinf #小数点切り上げ、切り捨て、平方根
from copy import deepcopy #参照で影響されないコピー
from collections import Counter, deque #要素ごとの出現回数、双方向アクセス可能データ型
import heapq
import numpy as np
from functools import reduce
sys.setrecursionlimit(200000)

input = sys.stdin.readline
# template


n, k = map(int, input().split())
h = np.array([int(x) for x in input().split()])

dp = np.array([0] * n)

for i in range(1, n):
    j = max(0, i-k)
    dp[i] = np.min(np.abs(h[i] - h[j:i]) + dp[j:i])

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

import itertools
import numpy as np 
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
# -------------------
n, m, k = map(int, readline().split())
#print(n)
a = list(map(int, readline().split()))
b = list(map(int, readline().split()))
a = [0] + a
b = [0] + b
acc = list(itertools.accumulate(a))
bcc = list(itertools.accumulate(b))

#acc = np.array(acc)
#print(acc)
#bcc = np.array(bcc)

ans = 0

for i, val in enumerate(acc):
  if (val > k):
    break
  else:
    rest = k - val
    #print(rest)
    for j, val2 in enumerate(bcc):
      if (val2 <= rest):
        ans = max(ans, j + i)
      else:
        break

print(ans)
  


### FIXED CODE ###

import itertools
import numpy as np 
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
# -------------------
n, m, k = map(int, readline().split())
#print(n)
a = list(map(int, readline().split()))
b = list(map(int, readline().split()))
a = [0] + a
b = [0] + b
acc = list(itertools.accumulate(a))
bcc = list(itertools.accumulate(b))

#acc = np.array(acc)
#print(acc)
#bcc = np.array(bcc)

ans = 0
j = m
for i, val in enumerate(acc):
  if (val > k):
    break
  else:
    rest = k - val
    #print(rest)
    #j = m
    #一ループ目がJの最大になるので、外側に置いてOK
    while (bcc[j] > rest):
      j -= 1

    ans = max(ans, j + i)


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

from fractions import gcd

# mod. m での a の逆元 a^{-1} を計算する
# b * a^{-1} (mod m)を計算したい場合はb * modinv(a, m) % m
def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = int(a / b)
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u

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

lcm = A[0]
for i in range(1, N):
    lcm = lcm * A[i] // gcd(lcm, A[i])

print(sum([(lcm * modinv(x, int(1e9+7)) % int(1e9+7)) for x in A]) % int(1e9+7))

### FIXED CODE ###

from fractions import gcd
import collections
from collections import defaultdict

# mod. m での a の逆元 a^{-1} を計算する
# b * a^{-1} (mod m)を計算したい場合はb * modinv(a, m) % m
def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = int(a / b)
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u
    
# 途中計算でmodを計算する高速な累乗計算
def pow_k_mod(x, n, m):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
            K %= m
        x *= x
        x %= m
        n //= 2

    return (K * x) % m
    
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

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

factor = defaultdict(lambda: -1)
for i in range(N):
    c = collections.Counter(prime_factorize(A[i]))
    for k, v in c.items():
        factor[k] = max(factor[k], v)

lcm = 1
for k, v in factor.items():
    lcm *= pow_k_mod(k, v, int(1e9+7))
    lcm %= int(1e9+7)

print(sum([(lcm * modinv(x, int(1e9+7)) % int(1e9+7)) for x in A]) % int(1e9+7))
### BUGGY CODE ###

N,M = map(int,input().split())
N += 1
S = tuple(map(lambda x: x == '0', input()))

dp = [float('inf')]*N
dp[-1] = 0

for i in reversed(range(N-1)):
    if S[i]:
        dp[i] = min(dp[i+1:min(N,i+M+1)])+1
if dp[0] == float('inf'):
    print(-1)
    exit()

dp += [float('inf')]*(M+1)
res = []
i = 0
while i < N-1:
    t = dp[i]
    s = min(k for k in range(1,M+1) if dp[i+k]==t-1)
    res.append(s)
    i += s
print(*res)

### FIXED CODE ###


"""
演算子は要素とセットでモノイドを形成するようなものでなければならない。
すなわち、結合律が成り立ち単位元が存在する必要がある。

equalityはsetを高速化するために使う。めんどい場合はNoneにしてもOK
"""
class SegmentTree:

    @classmethod
    def all_identity(cls, operator, equality, identity, size):
        return cls(operator, equality, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, equality, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, equality, identity, data)

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, operator, equality, identity, data):
        if equality is None:
            equality = lambda a,b: False
        self.op = operator
        self.eq = equality
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        eq = self.eq
        while i and not eq(data[i],v):
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return iter(self.data[self.size:])

from operator import eq

N,M = map(int,input().split())
N += 1
S = tuple(map(lambda x: x == '0', input()))

dp = SegmentTree.all_identity(min, eq, float('inf'), N)
dp[N-1] = 0

for i in reversed(range(N-1)):
    if S[i]:
        dp[i] = dp[i+1:min(N,i+M+1)]+1
if dp[0] == float('inf'):
    print(-1)
    exit()

res = []
i = 0
while i < N-1:
    t = dp[i]
    k = 1
    while dp[i+k] != t-1:
        k += 1
    res.append(k)
    i += k
print(*res)
### BUGGY CODE ###


def digits_of(n):
    digits = []
    while n != 0:
        r = n % 10
        digits.append(r) 
        n = n // 10 
    return digits

def is_multiple_of_9 (n):
    sum = 0
    for i in digits_of (n):
        sum += i
    if sum % 9 == 0:
        print("Yes")
    else:
        print("No")

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

main()

### FIXED CODE ###

def main():
    n = int(input())
    if n == 0:
        print("Yes")
    elif n % 9 == 0:
        print("Yes")
    else:
        print("No")

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

ans = 0
for i in range(60):
    one = 0
    for a in A:
        if (a & (1 << i) != 0):
            one += 1
    zero = N - one
    now = one * zero % mod
    ans += now * pow(2, i) % mod
    ans %= mod
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

ans = 0
for i in range(60):
    one = 0
    for a in A:
        if (a & (1 << i) != 0):
            one += 1
    zero = N - one
    now = one * zero % mod
    ans += now * pow(2, i) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

import bisect
N = int(input())
Ln = list(map(int,input().split(' ')))
Ln.sort(reverse=True)

count = 0

def binary_area_search(target_list: list, target_item: int) -> int:
    '''
    @params
    target_list: [1,3,5](ACC)
    target_item: 2

    @return
    return index
    '''
    low = 0
    high = len(target_list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = target_list[mid]
        if guess > target_item:
            if mid == 0:
                return 0
            if target_item > target_list[mid-1]:
                return mid 
            high = mid -1
        else:
            if mid == len(target_list) - 1:
                return None
            if target_list[mid+1] > target_item:
                return mid + 1 
            low = mid + 1
    return None


def binary_area_search(target_list: list, target_item: int) -> int:
    '''
    @params
    target_list: [5,3,1](DESC)
    target_item: 2

    @return
    return index
    '''
    low = 0
    high = len(target_list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = target_list[mid]
        if guess > target_item:
            if mid == 0:
                return 0
            if target_item > target_list[mid-1]:
                return mid 
            high = mid -1
        else:
            if mid == high:
                return None
            if target_list[mid+1] > target_item:
                return mid + 1 
            low = mid + 1
    return None



for a in range(N):
    a_l = Ln[a]
    '''
    N^2*logN
    '''
    for b in range(a+1, N):
        b_l = Ln[b]
        c_threshold = a_l - b_l
        c_list = Ln[b+1:N]
        c_list.reverse()
        c_idx = bisect.bisect_right(c_list,c_threshold)
        #c_idx = binary_area_search(c_list,c_threshold)
        if c_idx is not None:
            count += len(c_list) - c_idx
    '''
    N^2
    '''
    '''
    current_min = N-1
    b = a +1
    while b <= current_min:
        c_idx = current_min
        bc = Ln[b] + Ln[c_idx]
        if a_l < bc:
            count += (current_min - b)
            b += 1
            continue
        current_min -= 1
    '''
print(count)

### FIXED CODE ###

N = int(input())
Ln = list(map(int,input().split(' ')))
Ln.sort(reverse=True)

count = 0
for a in range(N):
    a_l = Ln[a]
    current_min = N-1
    b = a +1
    while b <= current_min:
        c_idx = current_min
        bc = Ln[b] + Ln[c_idx]
        if a_l < bc:
            count += (current_min - b)
            b += 1
            continue
        current_min -= 1
    '''
    for b in range(a+1, N):
        if b >= current_min:
            break
        for c in range(b+1,N):
            c_idx = current_min
            bc = Ln[b] + Ln[c_idx]
            if a_l < bc:
                count += (current_min - b)
                break
            current_min -= 1
    '''
print(count)
### BUGGY CODE ###

import math

result = 0
K = int(input())
for i in range(K):
  for j in range(K):
    for k in range(K):
      a = i+1
      b = j+1
      c = k+1
      num = math.gcd(a,b)
      num2 = math.gcd(num,c)
      result += num2
print(result)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
  
result = 0
K = int(input())
for i in range(K):
  for j in range(K):
    for k in range(K):
      a = i+1
      b = j+1
      c = k+1
      num = gcd(a,b)
      num2 = gcd(num,c)
      result += num2
print(result)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
s = list(set(l))
all_sum = 0
count = {}
for i in range(len(s)):
    v = l.count(s[i])
    if v > 1:
        all_sum += v * (v - 1) // 2
        count[s[i]] = v
for i in range(len(l)):
    if l[i] in count:
        v = count[l[i]]
        print(all_sum - v * (v-1) // 2 + (v-1) * (v-2)//2)
    else:
        print(all_sum)

### FIXED CODE ###

import collections

def count_defaultdict(it):
    counter = collections.defaultdict(int)
    for x in it:
        counter[x] += 1
    return dict(counter)

_ = int(input())
l = list(map(int, input().split()))
all_sum = 0
count = count_defaultdict(l)
for _, v in count.items():
    all_sum += v * (v - 1) // 2
for i in range(len(l)):
    if count[l[i]] > 1:
        v = count[l[i]]
        print(all_sum - v * (v-1) // 2 + (v-1) * (v-2)//2)
    else:
        print(all_sum)
### BUGGY CODE ###

def f(x, m):
    return x%m

n, x, m = map(int, input().split())
A = [x]
ans = x

for i in range(1,n):
    buf = f(A[i-1]**2, m)
    if buf in A:
        idx = A.index(buf)
        back = len(A) - idx
        nokori = n-len(A)
        sumKurikaeshi = sum(A[idx:])
        ans += int(nokori/back)*sumKurikaeshi
        last = nokori%back
        for j in range(last):
            ans += A[idx+j]
        break
        
    else:
        A.append(buf)
        ans += buf

print(ans)

### FIXED CODE ###

n, x, m = map(int, input().split())
A = [x]
checkA = {x}
ans = x

for i in range(1,n):
    buf = A[i-1]*A[i-1] % m
    if buf in checkA:
        idx = A.index(buf)
        back = len(A) - idx
        nokori = n-len(A)
        sumKurikaeshi = sum(A[idx:])
        ans += int(nokori/back)*sumKurikaeshi
        last = nokori%back
        ans += sum(A[idx:idx+last])
        break
    else:
        A.append(buf)
        checkA.add(buf)
        ans += buf

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

N = int(input())
a = list(map(int,input().split()))
A = [i+1 for i in range(N)]

k = 0
for i in range(N):
  if a[i] == min(A):
    A.remove(a[i])
    k += 1
if k != 0:
  print(N - k)
else:
  print(-1)

### FIXED CODE ###

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

k = 0
L = 1
for i in range(N):
  if a[i] == L:
    k += 1
    L += 1
if k != 0:
  print(N - k)
else:
  print(-1)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
B=sorted(A)
for i in A:
    if max(A)==i:
        print(B[-2])
    else:
        print(max(A))

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
B=sorted(A)
C=max(A)
for i in A:
    if C==i:
        print(B[-2])
    else:
        print(C)
### BUGGY CODE ###

import sys, os, math, bisect, itertools, collections, heapq, queue
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A, B, C = sorted(il()), sorted(il()), sorted(il())

    ret = 0
    for a in A:
        b = bisect.bisect_left(B, a+1)
        if len(B) == b: break
        for mi in B[b:]:
            c = bisect.bisect_left(C, mi+1)
            ret += len(C) - c
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
import math
import bisect

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = sorted(il())
    B = sorted(il())
    C = sorted(il())

    ret = 0
    for b in B:
        al = bisect.bisect_right(A, b-1)
        cl = len(C) - bisect.bisect_left(C, b+1)
        ret += al*cl
    print(ret)


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


n = int(input())
a = list(map(int, input().split()))
b = set(a)
s = [0]*(n+1)

def choose2(x):
    return int(x*(x-1)/2)


for i in b:
    s[i] = a.count(i)
    
total = 0
for i in s:
    total += choose2(i)


for i in a:
    ans = 0
    ans = total - choose2(s[i]) + choose2(s[i]-1)
    print(ans)



### FIXED CODE ###


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

from collections import Counter
count = Counter(a)

def choose2(x):
    return int(x*(x-1)/2)
    
total = 0
for i in list(count.values()):
    total += choose2(i)

for i in a:
    s = count[i]
    print(total - choose2(s) + choose2(s-1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
g = [[] for _ in range(n)]

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

q = int(input())
v = []
d = []
c = []

query = [list(map(int, input().split())) for _ in range(q)]
query = query[::-1]

color = [0] * n

def dfs(node, dist, dist_max, col):
    if dist > dist_max:
        return
    if color[node] == 0:
        color[node] = col
    for next_node in g[node]:
        dfs(next_node, dist+1, dist_max, col)

for v, d, c in query:
    v -= 1
    dfs(v, 0, d, c)

for co in color:
    print(co)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
g = [[] for _ in range(n)]

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

q = int(input())

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

color = [0] * n
depth = [-1] * n

def dfs(node, dist, col, pre_node):
    if dist <= depth[node]:
        return
    depth[node] = dist
    if color[node] == 0:
        color[node] = col
    if dist == 0:
        return
    for next_node in g[node]:
        if next_node == pre_node:
            continue
        dfs(next_node, dist-1, col, node)

for v, d, c in query[::-1]:
    v -= 1
    dfs(v, d, c, -1)

for co in color:
    print(co)
### BUGGY CODE ###

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

tree = [[i] for i in range(N+1)]
tree_parent = [[] for i in range(N+1)]
points = [0] * N

for i in range(1, N):
  a, b = map(int, input().split())
  tree[a].append(b)
  tree_parent[b].append(a)  
  for parent in tree_parent[a]:
    tree[parent].append(b)
    
for i in range(Q):
  p, x = map(int, input().split())
  for node in tree[p]:
    points[node-1] += x
    
for point in points:
  print(point, end=" ")

### FIXED CODE ###

n,q = map(int,input().split())
rl = [0] * n
scores = [0] * n
for i in range(n-1):
    a,b = map(int,input().split())
    rl[b-1] = a-1
for j in range(q):
    p,x = map(int,input().split())
    scores[p-1] += x
for k in range(1,n):
    scores[k] += scores[rl[k]]
print(*scores)
### BUGGY CODE ###

INF = 1_000_000_007


def comb(n, k):
    k = min(n - k, k)
    if n == 0 or k == 0:
        return 1
    a = n
    for i in range(n - 1, n - k, -1):
        a *= i
    b = 1
    for i in range(2, k + 1):
        b *= i
    return a // b


N, M = list(map(int, input().split()))
A = [-1] + [int(input()) for _ in range(M)] + [N + 1]
res = 1
for i in range(M + 1):
    t = A[i + 1] - A[i] - 2
    if t < 0:
        res = 0
    else:
        _t = 0
        for i in range(t // 2 + 1):
            _t += comb(t - i, i)
        res *= _t
print(res % INF)


### FIXED CODE ###

MOD = 10 ** 9 + 7
N, M = list(map(int, input().split()))
B = [True] * (N + 1)
D = [1] + [0] * N
for _ in range(M):
    a = int(input())
    B[a] = False
for i in range(N):
    for j in range(i + 1, min(N, i + 2) + 1):
        if B[j]:
            D[j] = (D[j] + D[i]) % MOD
print(D[N])
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=z+1,0,~z,0;i,j=s//w+y[x],s%w+y[~x];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc159/tasks/abc159_e
import sys

ans = sys.maxsize
H, W, K = map(int, input().split())
s = [input() for _ in range(H)]

for h in range(1 << (H - 1)):
    g = 0
    ids = [-1 for _ in range(H)]
    for i in range(H):
        ids[i] = g
        if (h >> i) & 1:
            g += 1

    g += 1
    c = [[0] * W for _ in range(g)]
    for i in range(H):
        for j in range(W):
            c[ids[i]][j] = c[ids[i]][j] + (s[i][j] == '1')

    num = g - 1
    now = [0 for _ in range(g)]


    def add(j):
        for i in range(g):
            now[i] += c[i][j]

        for i in range(g):
            if now[i] > K:
                return False

        return True


    if num >= ans:
        continue

    for j in range(W):
        if not add(j):
            num += 1
            if num >= ans:
                continue
            now = [0 for _ in range(g)]
            if not add(j):
                num = sys.maxsize
                break

    ans = min(ans, num)

print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc159/tasks/abc159_e
import sys

ans = sys.maxsize
H, W, K = map(int, input().split())
s = [input() for _ in range(H)]

for h in range(1 << (H - 1)):
    g = 0
    ids = [-1 for _ in range(H)]
    for i in range(H):
        ids[i] = g
        if (h >> i) & 1:
            g += 1

    g += 1
    c = [[0 for _ in range(W)] for _ in range(g)]
    for i in range(H):
        for j in range(W):
            c[ids[i]][j] = c[ids[i]][j] + (s[i][j] == '1')

    num = g - 1
    now = [0 for _ in range(g)]


    def add(j):
        for i in range(g):
            now[i] += c[i][j]

        for i in range(g):
            if now[i] > K:
                return False

        return True

    if num >= ans:
        continue

    for j in range(W):
        if not add(j):
            num += 1
            if num >= ans:
                continue
            now = [0 for _ in range(g)]
            if not add(j):
                num = sys.maxsize
                break

    ans = min(ans, num)

print(ans)