Problem : 267 - Raisins

Problem Statistics

Solved Member: 27　　Submission: 44　　User Tried: 28

Statement:

邦妮，普洛的夫著名的巧克力製造商，需要將一整塊含有葡萄乾的巧克力進行切割。巧克力塊是一個由許多大小相等的正方形切片所組成的矩形。這些切片和巧克力的邊界對其，且排列在N列M欄上，因此共有N*M個切片。每一個切片上有一個或更多個葡萄乾，且沒有葡萄乾會位於兩個切片之間或橫跨兩個切片。

剛開始時，巧克力是一個單一完整的區塊，邦妮需要將他切成越來越小的區塊，直到他將整個巧克力切割成N*M個切片為止。由於邦妮非常的忙碌，他需要他的助手，史萊彼得，幫忙切割的工作。彼得只進行直線，且終端到終端的切割，同時他希望每一次切割後都能獲得報酬。由於邦妮手上沒有錢，所以他提議用葡萄乾作為彼得的報酬。史萊彼得同意了這項安排，但必須滿足下列的條件：每次他將一個區塊的巧克力切割成兩個較小的區塊時，他所得到的報酬，必須和原有區塊上面葡萄乾的數目相同。

邦妮希望付給彼得越少的報酬越好。他知道每一個切片上有多少個葡萄乾。他可以決定將區塊交給彼得切割的順序，並且可以告訴彼得如何切割(水平或垂直)，以及在何處切割。請幫助邦妮決定如何將巧克力塊切隔成個別的切片，且付給彼得的葡萄乾數越少越好。

Input:Output:

第一行有兩個整數N和M(1 ≤ N,M ≤ 50)。

接下來有N行，每行M個數。第i+1行的第j個數就是題目描述中的第i行第j欄個切片上的葡萄乾樹木，每個數字皆為正整數且不超過1000。

輸出一個數字表示最小花費。

Sample Input:Sample Output:

2 3
2 7 5
1 9 5

HINT:

Source:

IOI 2009

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1500ms	131072kb
1	1500ms	131072kb	5
2	1500ms	131072kb	5
3	1500ms	131072kb	5
4	1500ms	131072kb	5
5	1500ms	131072kb	5
6	1500ms	131072kb	5
7	1500ms	131072kb	5
8	1500ms	131072kb	5
9	1500ms	131072kb	5
10	1500ms	131072kb	5
11	1500ms	131072kb	5
12	1500ms	131072kb	5
13	1500ms	131072kb	5
14	1500ms	131072kb	5
15	1500ms	131072kb	5
16	1500ms	131072kb	5
17	1500ms	131072kb	5
18	5000ms	131072kb	5
19	5000ms	131072kb	5
20	5000ms	131072kb	5