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 $ k $ 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 $ n $ dni. Pomóż mu wybrać, na jakie dni zlecić produkcję $ k $ 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.

Input Format

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $ n $ oraz $ k $ ($1 \le k \le n \le 500\,000$). Drugi wiersz zawiera $ n $ dodatnich liczb całkowitych nieprzekraczających $10^{9}$ - koszty wytłoczenia płyty w kolejne dni. Trzeci wiersz zawiera $ n $ dodatnich liczb całkowitych nieprzekraczających $10^{9}$ - koszty pokrycia płyty brokatem w kolejne dni.

Output Format

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

Example

Input

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

Output

32

Notes

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.