Ban đầu, thanh sô cô la còn là một khối nguyên vẹn, Bonny cần cắt thanh này ra thành các mảnh nhỏ dần cho đến khi nhận được N x M miếng riêng biệt là các ô vuông đơn vị. Vì Bonny quá bận rộn, cô ta cần đến sự giúp đỡ của trợ lí Sly Peter của mình trong việc cắt thanh sô cô la này. Peter chỉ thực hiện việc cắt theo các đường thằng dọc/ ngang theo ranh giới giữa các ô. Các lắt cắt sẽ kéo dài từ đầu này đến đầu kìa của miếng sô cô la trên tay anh ta sao cho mỗi lát cắt chia miếng sô cô la thành 2. Peter muốn được trả tiền cho mỗi lát cắt anh ta thực hiên. Về phần mình, do Bonny không có sẵn tiền trong tay, nhưng có sẵn nhiều nho khô, nên cô ta đề nghị trả Peter bằng nho khô. Peter chấp nhận đề nghị này nhưng với một điều kiện : mỗi một lần anh ta cắt một miếng sô cô la thành 2 miếng nhỏ hơn, anh ta sẽ nhận được số nho khô bằng đúng số nho khô có trên miếng sô cô la anh ta từng cắt.

Bonny muốn trả Peter càng ít càng tốt. Cô ta biết số lượng hạt nho khô trên từng ô trong N x M ô vuông đơn vị của thanh sô cô la ban đầu. Cô có thể chọn thứu tự các miếng sô cô la để đưa cho Peter cắt và cô còn có quyền yêu cầu Peter cắt miếng sô cô la như thế nào (theo chiều dọc hay chiều ngang, đặt lát cắt thế nào ở vị trí nào). Bạn hãy giúp Bonny quyết định cách cắt thanh sô cô la thành các ô vuông đơn vị sao cho cô phải trả cho Petter số nho khô ít nhất có thể.

BÀI TOÁN

Hãy viết chương trình nhận vào số lượng hạt nho khô chứa trong mỗi ô vuông đơn vị, xác định số hạt nho khô tối thiểu mà Bonny sẽ trả cho Sly Peter.

GIỚI HẠN

1 ≤ N, M ≤ 50 Số lượng ô vuông đơn vị theo mỗi chiều của thanh sô cô la.

1 ≤ R_k.p ≤1000 Số lượng hạt nho khô chứa trong ô tại dòng thứ k và cột thứ p.

INPUT

Chương trình của bạn phải nhập từ standard input dữ liệu sau:

Dòng đầu tiên chứa các số nguyên N và M, cách nhau bởi một dấu cách.

N dòng tiếp theo mô tả có bao nhiêu hạt nho khô trên mỗi ô của thanh sô cô la. Dòng thứ k trong N dòng này mô ta dòng thứ k của thanh sô cô la. Mỗi dòng này chứa M số nguyên cách nhau bởi một dấu cách. Các số nguyên mô tả các ô vuông đơn vị của dòng tương ứng theo trình tự từ trái sang phải. Số thứ p trên dòng k (trong số N dòng này) cho bạn biết có bao nhiêu hạt nho khô chứa trong ô nằm tại dòng k, cột p của lưới.

OUTPUT

Chương trình của bạn phải xuất ra standard output, một dòng chứa một số nguyên duy nhất: số lượng nho khô tối thiểu Bonny phải trả cho Sly Peter.

CÁCH CHẤM ĐIỂM

Sẽ có một nhóm các test với tổng điểm là 25, trong đó N và M không vượt quá 7.

VÍ DỤ

Một trong số những cách đạt được chi phí 77 là:

Lát cắt đầu tiên mà Bonny yêu cầu thực hiện là cắt cột số 3 ra khỏi phần còn lại của thanh sô cô la. Bonny cần trả Peter 29 hạt nho khô vì việc này.

Sau đó, Bonny, đưa cho Peter miếng nhỏ hơn trong 2 miếng: là miếng có 2 ô với 5 hạt nho khô trong mỗi ô, và yêu cầu Peter cắt đôi. Chi phí Bonny phải trả là 10 hạt nho khô.

Tiếp theo, Bonny đưa Peter miếng lớn còn lại, miếng có các ô với số lượng nho khô tương ứng là 2,7,1 và 9. Bonny yêu cầu Peter cắt theo chiều ngang, tách dòng đầu và dòng thứ 2. Cô phải trả 19 hạt nho khô.

Tiếp tục, Bonny đưa cho Peter miếng trên trái, trả 9 hạt nho khô. Cuối cùng, Bonny yêu cầu Peter tách miếng dưới trái, trả 10 hạt nho khô.

Tổng cộng Bonny tốn hết 29 10 + 19 + 10 = 77 hạt nho khô. Không có cách cắt nào chia thanh sô cô la thành 6 ô với chi phí nhỏ hơn.

School@net