Archiwum zadań programistycznych WWSI

Jak zapewne wszyscy wiecie, albo i nie, w podziemiach Warszawskiej Wyższej Szkoły Informatyki jest bufet. W bufecie tym wszystkie sprzedawane produkty znajdują się na dwóch półkach i posortowane są niemalejąco w zależności od ceny. Dzięki takiemu ułożeniu towarów studenci mający n złotych, z łatwością odnajdują wszystkie produkty, na które mogą sobie pozwolić. Rozwiązanie to funkcjonowało sprawnie przez wiele lat, jednak ostatnimi czasy zaczęło wpływać coraz więcej skarg. Studenci narzekają, że muszą przeglądać produkty znajdujące się na dwóch półkach i zdecydowanie łatwiej byłoby gdyby wszystkie sprzedawane w bufecie rzeczy znajdowały się na jednej półce, oczywiście wciąż powinny być posortowane niemalejąco względem ceny.

Prowadzącym bufet nie pozostało nic innego, jak tylko spełnić prośby klientów i poprzekładać wszystkie towary na jedną półkę. Chcieliby zrobić to jak najniższym nakładem zarówno czasu jak i energii. Przełożenie produktu kosztującego 3 PLN z półki A na półkę B, na której obecnie znajdują się produkty kosztujące odpowiednio 1, 5, 7 PLN może kosztować 1 lub 2 jednostki czasu (wymaga odpowiednio przesunięcia jednego produktu w lewo albo dwóch produktów w prawo) można również wykonać całą operację w pomijalnie krótkim czasie przekładając rzeczy z półki B na półkę A. Należy bardzo starannie wybrać docelową półkę, gdyż dany produkt można przemieścić pomiędzy półkami jeden raz. Dla uproszczenia zakładamy, że czasochłonne jest jedynie przekładanie produktów w obrębie jednej półki. Przesunięcie jednego produktu w prawo lub lewo trwa jedną jednostkę czasu, przekładanie elementów pomiędzy półkami jest pomijalnie krótkie. Twoim zadaniem jest napisać program, który po wczytaniu cen produktów znajdujących się na obydwu półkach obliczy czas potrzebny do przeniesienia wszystkich rzeczy na jedną półkę. Należy założyć, że na obydwu półkach jest wystarczająco dużo miejsca, aby pomieścić wszystkie towary.

Wejście

W pierwszej linii wejścia znajdują się dwie liczby a oraz b (1 ≤ a, b ≤ 10⁶) oznaczające odpowiednio liczbę produktów znajdujących się na półce pierwszej oraz drugiej. W drugiej linii znajduje się a posortowanych niemalejąco liczb. Każda z liczb oznacza cenę danego produktu jaki znajduje się na półce pierwszej. W trzeciej linii znajduje się analogiczny opis dotyczący półki drugiej. Składa się on z b posortowanych niemalejąco liczb. Ceny nie przekraczają 100 PLN.

Wyjście

Na wyjściu należy wypisać jedną liczbę oznaczającą najkrótszy możliwy do uzyskania czas niezbędny na przeniesienie wszystkich produktów na jedną z półek.

Przykład

Wejście

4 6
2 6 12 16
4 9 10 25 29 33

Wyjście

5