[USACO11MAR] Brownie Slicing G

Bessie烘焙了一块巧克力蛋糕。这块蛋糕是由 $R\times C(1\leq R,C\leq 500)$ 个小的巧克力蛋糕组成的。第 $i$ 行，第 $j$ 列的蛋糕有 $N_{i,j}(N_{i,j}\leq 4000)$ 块巧克力碎屑。 Bessie想把蛋糕分成 $A\times B(1\leq A\leq R,1\leq B\leq C)$ 块，:给 $A\times B$ 只奶牛。蛋糕先水平地切 $A-1$ 刀（只能切沿整数坐标切）来把蛋糕划分成 $A$ 块。然后再把剩下来的每一块独立地切 $B-1$ 刀，也只能切沿整数坐标切。其他 $A\times B-1$ 只奶牛就每人选一块，留下一块给Bessie。由于贪心，他们只会留给Bessie巧克力碎屑最少的那块。求出Bessie最优情况下会获得多少巧克力碎屑。 例如，考虑一个$5\times4$的蛋糕，上面的碎屑分布如下图所示： ``` 1 2 2 1 3 1 1 1 2 0 1 3 1 1 1 1 1 1 1 1 ``` Bessie必须把蛋糕切成4条，每条分成2块。Bessie能像这样切蛋糕: ``` 1 2 | 2 1 --------- 3 | 1 1 1 --------- 2 0 1 | 3 --------- 1 1 | 1 1 1 1 | 1 1 ``` 这样，Bessie至少能获得 $3$ 块巧克力碎屑

Bessie has baked a rectangular brownie that can be thought of as an RxC grid (1 <= R <= 500; 1 <= C <= 500) of little brownie squares. The square at row i, column j contains N\_ij (0 <= N\_ij <= 4,000) chocolate chips. Bessie wants to partition the brownie up into A\*B chunks (1 <= A <= R; 1 <= B <= C): one for each of the A\*B cows. The brownie is cut by first making A-1 horizontal cuts (always along integer coordinates) to divide the brownie into A strips. Then cut each strip \*independently\* with B-1 vertical cuts, also on integer boundaries. The other A\*B-1 cows then each choose a brownie piece, leaving the last chunk for Bessie. Being greedy, they leave Bessie the brownie that has the least number of chocolate chips on it. Determine the maximum number of chocolate chips Bessie can receive, assuming she cuts the brownies optimally. As an example, consider a 5 row x 4 column brownie with chips distributed like this: ``` 1 2 2 1 3 1 1 1 2 0 1 3 1 1 1 1 1 1 1 1 ``` Bessie must partition the brownie into 4 horizontal strips, each with two pieces. Bessie can cut the brownie like this: ``` 1 2 | 2 1 --------- 3 | 1 1 1 --------- 2 0 1 | 3 --------- 1 1 | 1 1 1 1 | 1 1 ``` Thus, when the other greedy cows take their brownie piece, Bessie still gets 3 chocolate chips. Bessie烘焙了一块巧克力蛋糕。这块蛋糕是由R\*C(1 <= R,C <= 500)个小的巧克力蛋糕组成的。第i行，第j列的蛋糕有N\_ij(1<= N\_ij <= 4,000)块巧克力碎屑。 Bessie想把蛋糕分成A\*B块，(1 <= A<= R,1 <= B <= C): 给A\*B只奶牛。蛋糕先水平地切A-1刀（只能切沿整数坐标切）来把蛋糕划分成A块。然后再把剩下来的每一块独立地切B-1刀，也只能切沿整数坐标切。其他A\*B-1只奶牛就每人选一块，留下一块给Bessie。由于贪心，他们只会留给Bessie巧克力碎屑最少的那块。求出Bessie最优情况下会获得多少巧克力碎屑。 例如，考虑一个5\*4的蛋糕，上面的碎屑分布如下图所示： ``` 1 2 2 1 3 1 1 1 2 0 1 3 1 1 1 1 1 1 1 1 ``` Bessie必须把蛋糕切成4条，每条分成2块。Bessie能像这样切蛋糕:

\* Line 1: Four space-separated integers: R, C, A, and B \* Lines 2..R+1: Line i+1 contains C space-separated integers: N\_i1, ..., N\_iC

\* Line 1: A single integer: the maximum number of chocolate chips that Bessie guarantee on her brownie

5 4 4 2 
1 2 2 1 
3 1 1 1 
2 0 1 3 
1 1 1 1 
1 1 1 1 

3