Bonny, nghệ nhân làm sô-cô-la nổi tiếng của Plovdiv, cần cắt một thanh sô-cô-la có nho khô. Thanh sô-cô-la là một khối hình chữ nhật gồm các ô vuông giống hệt nhau, có các cạnh song song với cạnh của thanh sô-cô-la. Các ô được xếp thành \(N\) hàng và \(M\) cột, tổng cộng \(NM\) ô. Mỗi ô có ít nhất một quả nho khô; không có quả nho khô nào nằm giữa hai ô hoặc vắt qua ranh giới giữa các ô.

Ban đầu, thanh sô-cô-la là một khối liền. Bonny cần cắt nó thành những khối ngày càng nhỏ hơn, cho đến khi tách được toàn bộ \(NM\) ô riêng lẻ. Vì rất bận, Bonny cần người phụ việc Peter ranh mãnh giúp cắt. Peter chỉ thực hiện những đường cắt thẳng xuyên suốt khối từ cạnh này sang cạnh kia và muốn được trả công cho từng nhát cắt. Bonny không có sẵn tiền, nhưng còn rất nhiều nho khô, nên đề nghị trả công cho Peter bằng nho khô. Peter đồng ý, nhưng đặt ra điều kiện: mỗi khi cắt một khối sô-cô-la thành hai khối nhỏ hơn, anh ta phải được trả số quả nho khô bằng tổng số quả nho khô trên khối được đưa cho anh ta cắt.

Bonny muốn trả cho Peter ít nhất có thể. Cô biết số quả nho khô trên từng ô trong \(NM\) ô. Cô có thể chọn thứ tự đưa các khối còn lại cho Peter, đồng thời chỉ định hướng cắt (ngang hoặc dọc) và vị trí chính xác của từng đường cắt. Hãy giúp Bonny quyết định cách cắt thanh sô-cô-la thành các ô riêng lẻ để trả cho Peter ít nho khô nhất.

Nhiệm vụ

Cho số quả nho khô trên từng ô, hãy viết chương trình xác định số quả nho khô ít nhất mà Bonny phải trả cho Peter.

Dữ liệu vào

Chương trình đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai 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ả số quả nho khô trên mỗi ô của thanh sô-cô-la. Dòng thứ \(k\) trong số này mô tả hàng thứ \(k\), gồm \(M\) số nguyên cách nhau bởi một dấu cách, theo thứ tự các ô từ trái sang phải. Số nguyên thứ \(p\) trên dòng thứ \(k\) trong số \(N\) dòng này là số quả nho khô trên ô ở hàng \(k\), cột \(p\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: số quả nho khô ít nhất mà Bonny phải trả cho Peter.

Ràng buộc

• \(1 \le N, M \le 50\): số ô trên mỗi chiều của thanh sô-cô-la.
• \(1 \le R_{k,p} \le 1000\): số quả nho khô trên ô ở hàng \(k\), cột \(p\).

Phân nhóm

Bài có tổng cộng \(100\) điểm. Trong một số test có tổng cộng \(25\) điểm, cả \(N\) và \(M\) đều không vượt quá \(7\).

Ví dụ

2 3
2 7 5
1 9 5

77

    Không có cách cắt nào khác tách được thanh sô-cô-la thành $6$ ô riêng lẻ với chi phí nhỏ hơn.

Nguồn

IOI 2009.