Raper [A]

Limit pamięci: 256 MB

Znany bajtocki raper Bitbot planuje wydać specjalną edycję swojego ostatniego albumu "Bajty z głośnika". Nośnikiem mają być płyty gramofonowe (potocznie zwane winylami), po wytłoczeniu pokrywane brokatem.

Bitbot podpisał już umowy z tłocznią płyt oraz brokaciarnią (tj. firmą pokrywającą obiekty brokatem) na egzemplarzy swojego albumu. Zarówno tłocznia, jak i brokaciarnia jest w stanie przetworzyć tylko jeden winyl dziennie. Oczywiście każdy winyl musi najpierw być wytłoczony, a dopiero potem pokryty brokatem. Na szczęście jest możliwe przetworzenie tej samej płyty w obu firmach w ciągu jednego dnia.

Nasz raper duma teraz nad wykazem cen za skorzystanie z usług tłoczni oraz brokaciarni na najbliższe dni. Pomóż mu wybrać, na jakie dni zlecić produkcję płyt w obu fabrykach, aby zminimalizować łączne wydatki. Możesz założyć, że Bitbot może przechowywać wytłoczone, ale niepokryte brokatem płyty dowolnie długo, nie ponosząc dodatkowych kosztów.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite oraz (). Drugi wiersz zawiera dodatnich liczb całkowitych nieprzekraczających - koszty wytłoczenia płyty w kolejne dni. Trzeci wiersz zawiera dodatnich liczb całkowitych nieprzekraczających - koszty pokrycia płyty brokatem w kolejne dni.

Wyjście

Twój program powinien wypisać jedną liczbę całkowitą - minimalny koszt produkcji winyli pokrytych brokatem.

Przykład

Dla danych wejściowych:

8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1

poprawną odpowiedzią jest:

32

Wyjaśnienie do przykładu: Przykładowym optymalnym rozwiązaniem jest wytłoczenie i pokrycie brokatem pierwszej płyty pierwszego dnia, wytłoczenie drugiej drugiego dnia i pokrycie jej brokatem czwartego dnia, wytłoczenie trzeciej trzeciego dnia i pokrycie jej brokatem piątego dnia, oraz wytłoczenie czwartej płyty szóstego dnia i pokrycie jej brokatem ósmego dnia.

Autor zadania: Jakub Pachocki.