Rodzynki

Limit pamięci: 128 MB

Słynna producent czekolady z Plovdiv, Bonny, musi pociąć tabliczkę czekolady z rodzynkami. Czekolada jest prostokątem składającym się z jednakowych, kwadratowych kawałków. Kawałki są ułożone równolegle do krawędzi czekolady w rzędach i kolumnach, co daje łącznie kawałków. Każdy z kawałków zawiera pewną dodatnią liczbę rodzynek, a żadne rodzynki nie leżą na liniach oddzielających kawałki.

Początkowo czekolada jest w całości. Bonny chce ją ciąć na coraz mniejsze fragmenty, aż w końcu otrzyma czekoladę podzieloną na pojedynczych kawałków. Ponieważ Bonny jest bardzo zajęta, do pomocy przy cięciu potrzebuje pomocy swego asystenta, Chytrego Piotra. Piotr tnie czekoladę po prostych, od brzegu do brzegu, i oczekuje zapłaty za każde wykonane cięcie. Bonny chwilowo nie posiada pieniędzy, ma za to sporo rodzynek, które nie zostały użyte, więc oferuje Piotrowi zapłatę w rodzynkach. Chytry Piotr zgadza się, ale pod warunkiem, że za każde przecięcie fragmentu czekolady na dwa mniejsze dostanie tyle rodzynek, ile jest ich łącznie w tym fragmencie.

Bonny chciałaby dać Piotrowi jak najmniej rodzynek. Wie dokładnie, ile rodzynek jest w każdym z kawałków. Może też zadecydować o kolejności, w której będzie podawać Piotrowi fragmenty czekolady, a także kazać mu wykonywać cięcia w konkretnym kierunku (w pionie lub poziomie) i wzdłuż konkretnej linii. Pomóż Bonny znaleźć taki sposób cięcia czekolady na pojedyncze kawałki, żeby zapłaciła Chytremu Piotrowi jak najmniej rodzynek.

Zadanie

Napisz program, który mając dane liczby rodzynek w poszczególnych kawałkach czekolady, wyznaczy minimalną liczbę rodzynek, które Bonny będzie musiała oddać Chytremu Piotrowi.

Ograniczenia

- liczby kawałków na każdym z boków czekolady
- liczba rodzynek w kawałku czekolady w -tym wierszu i -tej kolumnie

Wejście

Twój program powinien wczytać ze standardowego wejścia następujące dane:

• Pierwszy wiersz zawiera liczby całkowite i , oddzielone pojedynczym odstępem.
• Kolejne wierszy zawiera informacje o rozmieszczeniu rodzynek w poszczególnych ka\-wał\-kach czekolady. -ty z tych wierszy opisuje -ty wiersz czekolady i zawiera liczb całkowitych pooddzielanych pojedynczymi odstępami. Liczby te opisują kawałki w danym wierszu, od lewej do prawej. -ta liczba w -tym wierszu (spośród wierszy, o których mowa) to liczba rodzynek, które znajdują się w kawałku czekolady w -tym wierszu i -tej kolumnie.

Wyjście

Twój program powinien wypisać na standardowe wyjście jeden wiersz zawierający jedną liczbę całkowitą: minimalną liczbę rodzynek, które Bonny musi oddać Chytremu Piotrowi.

Ocenianie

W testach wartych łącznie 25 punktów i nie przekroczą 7.

Przykład

Dla danych wejściowych:

2 3
2 7 5
1 9 5

poprawną odpowiedzią jest:

77

Wyjaśnienie do przykładu: oto jeden z możliwych sposobów (spośród wielu) osiągnięcia kosztu 77 rodzynek.

Pierwszym cięciem, o które prosi Piotra Bonny, jest oddzielenie trzeciej kolumny od reszty czekolady. Bonny płaci za to 29 rodzynek.

Następnie, Bonny daje Piotrowi mniejszy z fragmentów - ten złożony z dwóch kawałków zawierających po 5 rodzynek - a Piotr przecina go na pół za 10 rodzynek.

Później Bonny daje Piotrowi największy z pozostałych fragmentów - ten zawierający kawałki z 2, 7, 1 oraz 9 rodzynkami. Bonny prosi o poziome cięcie, które oddzieli pierwszy wiersz od drugiego, i płaci 19 rodzynek.

Następnie, Bonny daje Piotrowi lewy górny fragment, płacąc 9 rodzynek. W końcu Bonny prosi Piotra o podzielenie lewego dolnego fragmentu za 10 rodzynek.

Całkowity koszt, jaki ponosi Bonny, to rodzynek. Żaden inny schemat cięć nie podzieli tej czekolady na 6 kawałków mniejszym kosztem.