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.