Maximize the Minimum Nuts in Chocolate Pieces

You are given a rectangular chocolate bar divided into m rows and n columns. Each cell in the chocolate may or may not contain a nut. Your task is to cut the chocolate bar exactly k times (resulting in k rectangular pieces) by making straight cuts (horizontal or vertical). The goal is to maximize the minimum number of nut pieces among all the resulting pieces.

More formally, consider a chocolate bar represented by a 2D grid where each cell is either 1 (if it contains a nut) or 0 (if it does not). You are allowed to perform k-1 cuts, and after these cuts, each of the k pieces must have at least a certain number of nuts. You need to find the maximum possible value of that minimum number of nuts across the pieces.

The problem involves using techniques such as computing prefix sum arrays to quickly calculate the number of nuts in any subrectangle and then using a DFS (depth-first search) strategy combined with binary search to test the feasibility of a candidate answer.

inputFormat

The first line of input contains three integers m, n, and k separated by spaces.

This is followed by m lines, each containing n integers (each either 0 or 1), representing the chocolate bar grid. The integer 1 indicates a nut is present in that piece, and 0 indicates no nut.

Example:

3 3 4
1 0 0
0 1 0
0 0 1

outputFormat

Output a single integer — the maximum possible value of the minimum number of nut pieces in any resulting piece after making the k-1 cuts.

Example:

0

## sample

3 3 4
1 0 0
0 1 0
0 0 1

0