Czekolada

Limit pamięci: 32 MB

Dana jest tabliczka czekolady złożona z cząstek. Czekoladę należy połamać na pojedyncze cząstki. Kawałki czekolady możemy łamać wzdłuż pionowych i poziomych linii (zaznaczonych na rysunku liniami przerywanymi) wyznaczających podział czekolady na cząstki. Jedno przełamanie kawałka czekolady wzdłuż wybranej pionowej lub poziomej linii dzieli ten kawałek na dwa mniejsze. Każde przełamanie kawałka czekolady jest obarczone pewnym kosztem wyrażającym się dodatnią liczbą całkowitą. Koszt ten nie zależy od wielkości łamanego kawałka, a jedynie od linii wzdłuż której łamiemy. Oznaczmy koszty łamania wzdłuż kolejnych pionowych linii przez , a wzdłuż poziomych linii przez . Koszt połamania całej tabliczki na pojedyncze cząstki to suma kosztów kolejnych przełamań. Należy obliczyć minimalny koszt połamania całej tabliczki na pojedyncze cząstki.

Przykładowo, jeżeli połamiemy czekoladę przedstawioną na rysunku, najpierw wzdłuż linii poziomych, a następnie każdy z otrzymanych kawałków wzdłuż linii pionowych, to koszt takiego połamania wyniesie .

Zadanie

Napisz program, który:

• wczyta liczby i ,
• obliczy minimalny koszt połamania całej tabliczki na pojedyncze cząstki,
• wypisze wynik.

Wejście

W pierwszym wierszu standardowego wejścia zapisane są dwie dodatnie liczby całkowite i oddzielone pojedynczym odstępem, . W kolejnych wierszach zapisane są liczby , po jednej w wierszu, . W kolejnych wierszach zapisane są liczby , po jednej w wierszu, .

Wyjście

Twój program powinien pisać na standardowe wyjście. W pierwszym i jedynym wierszu Twój program powinien wypisać jedną liczbę całkowitą - minimalny koszt połamania całej tabliczki na pojedyncze cząstki.

Przykład

Dla danych wejściowych:

6 4
2
1
3
1
4
4
1
2

poprawną odpowiedzią jest:

42

Autor zadania: Marcin Kubica.