Pewna gra karciana, uważana za sprawdzian inteligencji, nosi nazwę „Kang”. W tej grze każda karta ma wartość punktową będącą dodatnią liczbą całkowitą. Na początku otrzymujesz $N$ kart do ręki, a kolejne $M$ kart leży odkrytych na stole w rzędzie od lewej do prawej. Widzisz wartości punktowe wszystkich kart — zarówno tych otrzymanych do ręki, jak i tych leżących na stole. Następnie możesz dobierać karty ze stołu przez kolejne $k$ rund, przy czym musisz dobierać po jednej karcie kolejno od lewej do prawej. Po dobraniu karty w każdej rundzie możesz 1 raz odrzucić karty z ręki — dowolną liczbę kart z ręki mających tę samą wartość punktową. Musisz tak zaplanować grę, aby po dobraniu kart ze stołu i odrzuceniu kart z ręki przez pełne $k$ rund, suma punktów kart pozostałych w ręce była jak najmniejsza.

Rozważmy następujący przykład:

Jeśli na początku masz pięć kart o wartościach punktowych $6, 3, 9, 6, 3$, a karty leżące na stole mają wartości od lewej do prawej równe $4, 6, 9, 6$:

Przypadek $k = 1$: Jeśli możesz dobrać ze stołu tylko 1 kartę, to po dobraniu pierwszej karty wartości punktowe posiadanych przez ciebie kart będą wynosić: $6, 3, 9, 6, 3, 4$. Następnie możesz 1 raz wybrać i odrzucić karty o tej samej wartości punktowej. Najlepszym wyborem jest odrzucenie 2 kart o wartości równej $6$, aby suma punktów pozostałych kart była najmniejsza i wynosiła $3 + 9 + 3 + 4 = 19$.

Przypadek $k = 2$: Jeśli możesz dobrać ze stołu 2 karty, najlepszym sposobem jest: po dobraniu pierwszej karty o wartości równej $4$ wybierasz odrzucenie jednej karty o wartości równej $9$. Pozostałe karty w ręce mają wartości $6, 3, 6, 3, 4$. Następnie, gdy dobierzesz 2. kartę o wartości równej $6$, będziesz mógł odrzucić 3 karty o wartości równej $6$, dzięki czemu pozostałe karty będą miały najmniejszą sumę punktów równą $3 + 3 + 4 = 10$.

Przypadek $k = 3$: Jeśli możesz dobrać ze stołu 3 karty, najlepszym sposobem jest: po dobraniu pierwszej karty wartości kart w ręce będą wynosić $6, 3, 9, 6, 3, 4$. Następnie możesz 1 raz wybrać karty o tej samej wartości do odrzucenia; najlepszym wyborem jest odrzucenie obu (2) kart o wartości równej $3$, co pozostawi w ręce karty $6, 9, 6, 4$. Następnie, gdy dobierzesz 2. kartę o wartości równej $6$, będziesz mógł odrzucić 3 karty o wartości równej $6$, co pozostawi w ręce karty $9, 4$. A gdy po raz 3. dobierzesz kartę o wartości równej $9$, będziesz mógł odrzucić obie (2) karty o wartości równej $9$, dzięki czemu suma punktów pozostałych kart wyniesie $4$.

Przypadek $k = 4$: Jeśli możesz dobrać ze stołu 4 karty, najlepszym sposobem jest: po dobraniu pierwszej karty o wartości równej $4$ wybierasz odrzucenie jednej karty o wartości równej $4$, co pozostawia w ręce karty o wartościach $6, 3, 9, 6, 3$. Następnie w 2. dobraniu karta ma wartość równą $6$; najlepszym wyborem jest odrzucenie obu (2) kart o wartości równej $3$, co pozostawi w ręce karty $6, 9, 6, 6$. W 3. dobraniu karta ma wartość równą $9$; wybierasz odrzucenie obu (2) kart o wartości równej $9$. A przy dobraniu ostatniej karty o wartości równej $6$ będziesz mógł odrzucić 4 karty o wartości równej $6$. To odrzucenie sprawi, że w ręce nie pozostanie żadna karta, co oznacza, że suma punktów kart wynosi $0$.

Twoje zadanie (Your Task)

Znajdź „najmniejszą sumę punktów kart pozostałych w ręce” po zakończeniu $k$ rund dla $k = 1, 2, 3, \ldots, M$.

To zadanie ma format programowania inny niż zwykle, który będzie używany podczas właściwych zawodów. Zapoznaj się z końcową częścią treści zadania, aby dowiedzieć się, jak z niego korzystać.

Szczegóły implementacji

Musisz napisać następującą funkcję:

std::vector<long long> capsize(std::vector<int> A, std::vector<int> B)

przyjmującą następujące parametry:

• $A$ to tablica długości $N$ określająca numery kart w ręce na początku.
• $B$ to tablica długości $M$ określająca numery kart leżących na stole, w kolejności od lewej do prawej.
• Funkcja ta musi zwrócić tablicę $C$ długości $M$, reprezentującą najmniejszą możliwą sumę punktów kart w ręce po $k$ rundach dla $k = 1, 2, 3, \ldots, M$.

Na przykład, jeśli $A = [6, 3, 9, 6, 3]$ oraz $B = [4, 6, 9, 6]$, funkcja musi zwrócić tablicę $[19, 10, 4, 0]$.

Ograniczenia

• $1 \le N, M \le 10^6$
• $1 \le A[i] \le 10^9$ dla każdego $i$ spełniającego $1 \le i \le N$
• $1 \le B[i] \le 10^9$ dla każdego $i$ spełniającego $1 \le i \le M$

Podzadania

Uwagi

Instrukcje dotyczące pisania programu

W tym zadaniu sposób pisania programu i wysyłania go do systemu sprawdzającego (Grader) różni się od ogólnego formatu programowania, w którym zawodnik musi napisać część wczytującą dane wejściowe oraz część wypisującą wynik. W tym zadaniu zawodnik musi napisać wyłącznie niezbędną część obliczeniową wewnątrz podanej funkcji. Dane wejściowe będą dostępne poprzez parametry funkcji, a wyniki obliczeń również muszą zostać zwrócone przez funkcję — zawodnik nie musi pisać części wczytującej dane wejściowe ani części wypisującej wynik.

Zawodnik otrzyma kilka następujących plików; musi zmodyfikować tylko jeden plik wskazany w zadaniu i wysłać ten plik do systemu:

• grader.cpp to główny plik odpowiedzialny za wczytywanie danych wejściowych i wypisywanie wyjściowych.
• kang.cpp to plik, w którym zawodnik musi napisać obliczenia programu, oraz plik, który zawodnik wysyła do systemu (w pliku kang.cpp nie wolno umieszczać funkcji main(), ale mogą znajdować się inne funkcje).
• run_cpp.sh to plik, którego zawodnik może użyć do uruchomienia całego programu.
• compile_cpp.sh to plik, którego zawodnik może użyć do skompilowania programu.

Zawodnik otrzyma plik .zip, który można pobrać z systemu; po jego rozpakowaniu (extract) znajdą się w nim wszystkie 4 pliki. Zawodnik powinien użyć edytora tekstu lub IDE do edycji pliku kang.cpp, a kompilację lub uruchomienie programu wykonać poprzez wywołanie compile_cpp.sh lub run_cpp.sh.

Gdy zawodnik wywoła plik run_cpp.sh w celu uruchomienia programu, program zadziała zgodnie z opisem w pliku grader.cpp, którego sekcja „Opis pliku sprawdzarki” wyjaśnia działanie tego pliku.