====== 행렬분할 ======

===== 풀이 =====
  * [[ps:problems:boj:23331]]의 쉬운 버전. [[ps:problems:boj:23331]]에서는 n이 최대 100이라서 [[ps:이진_검색#파라메트릭 서치]]를 사용해야만 했는데, 여기에서는 그냥 백트래킹으로 다 해봐도 답을 구할 수 있는것 같다. 하지만, 그렇게 구현하지는 않았고, 그냥 [[ps:problems:boj:23331]]의 코드를 그대로 재사용했다.
  * 풀이는 [[ps:problems:boj:23331]] 참고.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 23318. 행렬분할".

- Problem link: https://www.acmicpc.net/problem/23318
- Solution link: http://www.teferi.net/ps/problems/boj/23318

Tags: [Parametric search]
"""

import itertools
import functools
from teflib import binsearch

INF = float('inf')


def can_divide(sum_limit, remaining_div_count, mat):
    sums = [0] * (len(mat[0]))
    for nums in mat:
        sums = [s + n for s, n in zip(sums, nums)]
        if any(s > sum_limit for s in sums):
            if any(n > sum_limit for n in nums):
                return False
            sums = nums
            remaining_div_count -= 1
            if remaining_div_count < 0:
                return False
    return True


def main():
    n, m = [int(x) for x in input().split()]
    a, b = [int(x) for x in input().split()]
    mat = [[int(x) for x in input().split()] for _ in range(n)]

    all_sum = sum(sum(row) for row in mat)
    answer = INF
    for partition in itertools.combinations(range(1, m), b):
        partition = (0, *partition, m)
        new_mat = [[
            sum(row[beg:end]) for beg, end in itertools.pairwise(partition)
        ] for row in mat]
        pred = functools.partial(can_divide, remaining_div_count=a, mat=new_mat)
        min_score = binsearch.minimum_valid_integer(0, all_sum, pred)
        answer = min(answer, min_score)

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:binsearch#minimum_valid_integer|teflib.binsearch.minimum_valid_integer]]

{{tag>BOJ ps:problems:boj:골드_5}}