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 x₁, x₂, ..., x_m-1, a wzdłuż poziomych linii przez y₁, y₂, ..., y_n-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.

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 y₁+y₂+y₃+4*(x₁+x₂+x₃+x₄+x₅).

Zadanie

Napisz program, który:

• wczyta liczby x₁, x₂, ..., x_m-1 i y₁, y₂, ..., y_n-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 x₁, x₂, ..., x_m-1, po jednej w wierszu, 1 <= x_i <= 1000. W kolejnych n-1 wierszach zapisane są liczby y₁, y₂, ..., y_n-1, po jednej w wierszu, 1 <= y_i <= 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