SIO Anonymous
wydruk ps pdf

Czekolada (cze)

Dana jest tabliczka czekolady złożona z m*n 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 x1, x2, ..., xm-1, a wzdłuż poziomych linii przez y1, y2, ..., yn-1. 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.

Czekolada z przykładu

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 y1+y2+y3+4*(x1+x2+x3+x4+x5).

Zadanie

Napisz program, który:

  • wczyta liczby x1, x2, ..., xm-1 i y1, y2, ..., yn-1,
  • 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 m i n oddzielone pojedynczym odstępem, 2 <= m,n <= 1000. W kolejnych m-1 wierszach zapisane są liczby x1, x2, ..., xm-1, po jednej w wierszu, 1 <= xi <= 1000. W kolejnych n-1 wierszach zapisane są liczby y1, y2, ..., yn-1, po jednej w wierszu, 1 <= yi <= 1000.

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

poprawnym wynikiem jest:

42

Nazwa pliku źródłowego: cze.XXX, gdzie XXX to c dla C, cpp dla C++, pas dla Pascala.
SIO, 2019-08-19 20:18:46