Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

def main():
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    if S.sum() <= K:
        print(0)
        exit(0)
    answer = (H - 1) * (W - 1)
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons)
        if result > 0 and result < answer:
            answer = result
    print(answer)

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(W, S, K, horizons):
    answer = sum(horizons)
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0))
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0))
    # ブロック毎の累積和を計算する
    left = 0
    right = 0
    partial_sums = [0] * len(S2)
    while right <= W - 1:
        satisfied = True
        for idx, row in enumerate(S2):
            partial_sums[idx] += row[right]
            # 無理(ブロックの中のホワイトチョコの数をk以下にできない)な場合
            if partial_sums[idx] > K:
                satisfied = False
                if left == right:
                    return -1
                left = right
                answer += 1
                partial_sums = [0] * len(S2)
                break
        if satisfied:
            right += 1
        # if satisfied:
        #     right += 1
        # else:
        #     # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
        #     if left == right:
        #         return -1
        #     left = right
        #     answer += 1
        #     partial_sums = [0] * len(S2)
    return answer

main()


Fixed submission:
import numpy as np

def main():
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    if S.sum() <= K:
        print(0)
        exit(0)
    answer = float('INF')
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons, answer)
        answer = min(answer, result)
    print(answer)

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(W, S, K, horizons, current_answer):
    answer = sum(horizons)
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0).tolist())
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0).tolist())
    # ブロック毎の累積和を計算する
    h = len(S2)
    partial_sums = [0] * h
    for right in range(W):
        current = [0] * h
        for idx in range(h):
            current[idx] = S2[idx][right]
            partial_sums[idx] += S2[idx][right]
        # 1列に含むホワイトチョコの数がkより多い場合
        if max(current) > K:
            return float('INF')
        # 無理な(ブロックの中のホワイトチョコの数をk以下にできない)場合
        if max(partial_sums) > K:
            answer += 1
            if answer >= current_answer:
                return float('INF')
            partial_sums = current
    return answer

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

def main():
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    if S.sum() <= K:
        print(0)
        exit(0)
    answer = (H - 1) * (W - 1)
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons)
        if result > 0 and result < answer:
            answer = result
    print(answer)

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(W, S, K, horizons):
    answer = sum(horizons)
    # greedyに縦線を引いていく
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0))
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0))
    left = 0
    right = 0
    partial_sums = [0] * len(S2)
    while right <= W - 1:
        if satisfy(K, S2, right, partial_sums):
            right += 1
        else:
            # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
            if left == right:
                return -1
            left = right
            answer += 1
            partial_sums = [0] * len(S2)
    return answer

def satisfy(K, S2, right, partial_sums):
    result = True
    for idx, row in enumerate(S2):
        partial_sums[idx] += row[right]
        if partial_sums[idx] > K:
            result = False
    return result

main()


Fixed submission:
import numpy as np

def main():
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    if S.sum() <= K:
        print(0)
        exit(0)
    answer = float('INF')
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons, answer)
        answer = min(answer, result)
    print(answer)

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(W, S, K, horizons, current_answer):
    answer = sum(horizons)
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0).tolist())
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0).tolist())
    # ブロック毎の累積和を計算する
    h = len(S2)
    partial_sums = [0] * h
    for right in range(W):
        current = [0] * h
        for idx in range(h):
            current[idx] = S2[idx][right]
            partial_sums[idx] += S2[idx][right]
        # 1列に含むホワイトチョコの数がkより多い場合
        if max(current) > K:
            return float('INF')
        # 無理な(ブロックの中のホワイトチョコの数をk以下にできない)場合
        if max(partial_sums) > K:
            answer += 1
            if answer >= current_answer:
                return float('INF')
            partial_sums = current
    return answer

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

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

if S.sum() <= K:
    print(0)
    exit(0)

def satisfy(left, right, S2):
    global K
    for row in S2:
        if row[left:(right + 1)].sum() > K:
            return False
    return True

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(horizons):
    global W, S
    answer = sum(horizons)
    left = 0
    right = 0
    # greedyに縦線を引いていく
    # TODO: 横線で分けた後のそれぞれのブロックで集計
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0))
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0))
    while right <= W - 1:
        if not satisfy(left, right, S2):
            # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
            if left == right:
                return -1
            left = right
            answer += 1
        else:
            right += 1
    return answer

answer = (H - 1) * (W - 1)

# result = greedy([0, 1, 0])

for i in range(0, 2 ** (H - 1)):
    horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
    result = greedy(horizons)
    if result > 0 and result < answer:
        answer = result

print(answer)


Fixed submission:
import numpy as np

def main():
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    if S.sum() <= K:
        print(0)
        exit(0)
    answer = float('INF')
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons, answer)
        answer = min(answer, result)
    print(answer)

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(W, S, K, horizons, current_answer):
    answer = sum(horizons)
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0).tolist())
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0).tolist())
    # ブロック毎の累積和を計算する
    h = len(S2)
    partial_sums = [0] * h
    for right in range(W):
        current = [0] * h
        for idx in range(h):
            current[idx] = S2[idx][right]
            partial_sums[idx] += S2[idx][right]
        # 1列に含むホワイトチョコの数がkより多い場合
        if max(current) > K:
            return float('INF')
        # 無理な(ブロックの中のホワイトチョコの数をk以下にできない)場合
        if max(partial_sums) > K:
            answer += 1
            if answer >= current_answer:
                return float('INF')
            partial_sums = current
    return answer

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

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

if S.sum() <= K:
    print(0)
    exit(0)

def satisfy(left, right, S2):
    global K
    top = 0
    for row in S2:
        if row[left:(right + 1)].sum() > K:
            return False
    return True

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(horizons):
    global W, S
    answer = sum(horizons)
    left = 0
    right = 0
    # greedyに縦線を引いていく
    # TODO: 横線で分けた後のそれぞれのブロックで集計
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0))
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0))
    S2 = np.array(S2)
    # print(S2)
    # print('hoge')
    while right <= W - 1:
        if not satisfy(left, right, S2):
            # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
            if left == right:
                return -1
            left = right
            answer += 1
        else:
            right += 1
    return answer

answer = (H - 1) * (W - 1)

# result = greedy([0, 1, 0])

for i in range(0, 2 ** (H - 1)):
    horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
    result = greedy(horizons)
    if result > 0 and result < answer:
        answer = result

print(answer)


Fixed submission:
import numpy as np

def main():
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    if S.sum() <= K:
        print(0)
        exit(0)
    answer = float('INF')
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons, answer)
        answer = min(answer, result)
    print(answer)

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(W, S, K, horizons, current_answer):
    answer = sum(horizons)
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0).tolist())
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0).tolist())
    # ブロック毎の累積和を計算する
    h = len(S2)
    partial_sums = [0] * h
    for right in range(W):
        current = [0] * h
        for idx in range(h):
            current[idx] = S2[idx][right]
            partial_sums[idx] += S2[idx][right]
        # 1列に含むホワイトチョコの数がkより多い場合
        if max(current) > K:
            return float('INF')
        # 無理な(ブロックの中のホワイトチョコの数をk以下にできない)場合
        if max(partial_sums) > K:
            answer += 1
            if answer >= current_answer:
                return float('INF')
            partial_sums = current
    return answer

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

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

if S.sum() <= K:
    print(0)
    exit(0)

def satisfy(left, right, horizons):
    global K, S
    top = 0
    white_chocos = 0
    for idx, h in enumerate(horizons):
        white_chocos += S[idx, left:(right + 1)].sum()
        if h == 1:
            bottom = idx
            # total = S[top:(bottom + 1), left:(right + 1)].sum()
            # total = sum(map(lambda row: sum(row[left:(right + 1)]), S[top:(bottom + 1)]))
            # print(horizons, top, bottom, left, right, total)
            if white_chocos > K:
                return False
            top = bottom + 1
            white_chocos = 0
    total = S[top:, left:(right + 1)].sum()
    # total = sum(map(lambda row: sum(row[left:(right + 1)]), S[top:]))
    # print(horizons, top, -1, left, right, total)
    if total > K:
        return False
    return True

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(horizons):
    global W
    answer = sum(horizons)
    left = 0
    right = 0
    # greedyに縦線を引いていく
    # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
    while right <= W - 1:
        if not satisfy(left, right, horizons):
            if left == right:
                return -1
            left = right
            answer += 1
        else:
            right += 1
    return answer

answer = (H - 1) * (W - 1)

# result = greedy([0, 1, 0])

for i in range(0, 2 ** (H - 1)):
    horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
    result = greedy(horizons)
    if result > 0 and result < answer:
        answer = result

print(answer)


Fixed submission:
import numpy as np

def main():
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    if S.sum() <= K:
        print(0)
        exit(0)
    answer = float('INF')
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons, answer)
        answer = min(answer, result)
    print(answer)

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(W, S, K, horizons, current_answer):
    answer = sum(horizons)
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0).tolist())
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0).tolist())
    # ブロック毎の累積和を計算する
    h = len(S2)
    partial_sums = [0] * h
    for right in range(W):
        current = [0] * h
        for idx in range(h):
            current[idx] = S2[idx][right]
            partial_sums[idx] += S2[idx][right]
        # 1列に含むホワイトチョコの数がkより多い場合
        if max(current) > K:
            return float('INF')
        # 無理な(ブロックの中のホワイトチョコの数をk以下にできない)場合
        if max(partial_sums) > K:
            answer += 1
            if answer >= current_answer:
                return float('INF')
            partial_sums = current
    return answer

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

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

if sum(map(sum, S)) <= K:
    print(0)
    exit(0)

def satisfy(left, right, horizons):
    global K, S
    top = 0
    for idx, h in enumerate(horizons):
        if h == 1:
            bottom = idx
            total = S[top:(bottom + 1), left:(right + 1)].sum()
            # total = sum(map(lambda row: sum(row[left:(right + 1)]), S[top:(bottom + 1)]))
            # print(horizons, top, bottom, left, right, total)
            if total > K:
                return False
            top = bottom + 1
    total = S[top:, left:(right + 1)].sum()
    # total = sum(map(lambda row: sum(row[left:(right + 1)]), S[top:]))
    # print(horizons, top, -1, left, right, total)
    if total > K:
        return False
    return True

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(horizons):
    answer = sum(horizons)
    left = 0
    right = 0
    # greedyに縦線を引いていく
    # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
    while right <= W - 1:
        if not satisfy(left, right, horizons):
            if left == right:
                return -1
            left = right
            answer += 1
        else:
            right += 1
    return answer

answer = (H - 1) * (W - 1)

# result = greedy([0, 1, 0])

for i in range(0, 2 ** (H - 1)):
    horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
    result = greedy(horizons)
    if result > 0 and result < answer:
        answer = result

print(answer)


Fixed submission:
import numpy as np

def main():
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    if S.sum() <= K:
        print(0)
        exit(0)
    answer = float('INF')
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons, answer)
        answer = min(answer, result)
    print(answer)

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(W, S, K, horizons, current_answer):
    answer = sum(horizons)
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0).tolist())
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0).tolist())
    # ブロック毎の累積和を計算する
    h = len(S2)
    partial_sums = [0] * h
    for right in range(W):
        current = [0] * h
        for idx in range(h):
            current[idx] = S2[idx][right]
            partial_sums[idx] += S2[idx][right]
        # 1列に含むホワイトチョコの数がkより多い場合
        if max(current) > K:
            return float('INF')
        # 無理な(ブロックの中のホワイトチョコの数をk以下にできない)場合
        if max(partial_sums) > K:
            answer += 1
            if answer >= current_answer:
                return float('INF')
            partial_sums = current
    return answer

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(map(int, list(input()))))

if sum(map(sum, S)) <= K:
    print(0)
    exit(0)

def satisfy(left, right, horizons):
    global K, S
    top = 0
    for idx, h in enumerate(horizons):
        if h == 1:
            bottom = idx
            total = sum(map(lambda row: sum(
                row[left:(right + 1)]), S[top:(bottom + 1)]))
            # print(horizons, top, bottom, left, right, total)
            if total > K:
                return False
            top = bottom + 1
    total = sum(map(lambda row: sum(row[left:(right + 1)]), S[top:]))
    # print(horizons, top, -1, left, right, total)
    if total > K:
        return False
    return True

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(horizons):
    answer = sum(horizons)
    left = 0
    right = 0
    # greedyに縦線を引いていく
    # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
    while right <= W - 1:
        if not satisfy(left, right, horizons):
            if left == right:
                return -1
            left = right
            answer += 1
        else:
            right += 1
    return answer

answer = (H - 1) * (W - 1)

# result = greedy([0, 1, 0])

for i in range(0, 2 ** (H - 1)):
    horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
    result = greedy(horizons)
    if result > 0 and result < answer:
        answer = result

print(answer)


Fixed submission:
import numpy as np

def main():
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    if S.sum() <= K:
        print(0)
        exit(0)
    answer = float('INF')
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons, answer)
        answer = min(answer, result)
    print(answer)

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(W, S, K, horizons, current_answer):
    answer = sum(horizons)
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0).tolist())
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0).tolist())
    # ブロック毎の累積和を計算する
    h = len(S2)
    partial_sums = [0] * h
    for right in range(W):
        current = [0] * h
        for idx in range(h):
            current[idx] = S2[idx][right]
            partial_sums[idx] += S2[idx][right]
        # 1列に含むホワイトチョコの数がkより多い場合
        if max(current) > K:
            return float('INF')
        # 無理な(ブロックの中のホワイトチョコの数をk以下にできない)場合
        if max(partial_sums) > K:
            answer += 1
            if answer >= current_answer:
                return float('INF')
            partial_sums = current
    return answer

if __name__ == '__main__':
    main()