Ett kortspel som sägs vara ett intelligenstest heter ”Kang”. I detta spel har varje kort en poäng som är ett positivt heltal. I början får du $N$ kort att hålla på handen, och det finns ytterligare $M$ kort som ligger öppna på bordet i rad från vänster till höger, där du kan se poängen på alla kort — både de du fått på handen och de som ligger på bordet. Därefter får du dra fler kort från bordet under $k$ rundor, där du måste dra ett kort i taget i ordning från vänster till höger. Efter att du dragit ett kort i varje runda kan du slänga kort från handen 1 gång — valfritt antal kort på handen som har samma poäng. Du måste planera ditt spel så att efter att du dragit kort från bordet och slängt kort från handen i $k$ rundor, har de kort som finns kvar på handen så liten poängsumma som möjligt.

Betrakta följande exempel:

Om du i början har fem kort med poängen $6, 3, 9, 6, 3$ och korten som ligger på bordet från vänster till höger har poängen $4, 6, 9, 6$:

Fallet $k = 1$: Om du bara får dra 1 kort från bordet kommer poängen på dina kort när du dragit det första kortet att vara $6, 3, 9, 6, 3, 4$. Därefter kan du välja att slänga kort med samma poäng 1 gång. Det bästa sättet är att välja att slänga 2 kort med poäng lika med $6$, så att poängsumman för de återstående korten blir så liten som möjligt, nämligen $3 + 9 + 3 + 4 = 19$.

Fallet $k = 2$: Om du får dra 2 kort från bordet är det bästa sättet: efter att ha dragit det första kortet med poäng lika med $4$ väljer du att slänga ett kort med poäng lika med $9$. De återstående korten på handen har poängen $6, 3, 6, 3, 4$. När du sedan drar det 2:a kortet med poäng lika med $6$ kan du slänga 3 kort med poäng lika med $6$, vilket gör att de återstående korten får minsta möjliga poängsumma lika med $3 + 3 + 4 = 10$.

Fallet $k = 3$: Om du får dra 3 kort från bordet är det bästa sättet: när du drar det första kortet blir poängen på korten på handen $6, 3, 9, 6, 3, 4$. Därefter kan du välja kort med samma poäng att slänga 1 gång, och det bästa sättet är att slänga båda (2) korten med poäng lika med $3$, så att korten $6, 9, 6, 4$ blir kvar på handen. När du sedan drar det 2:a kortet med poäng lika med $6$ kan du slänga 3 kort med poäng lika med $6$, så att du har korten $9, 4$ på handen. Och när du för 3:e gången drar ett kort med poäng lika med $9$ kan du slänga båda (2) korten med poäng lika med $9$, vilket gör att de återstående korten får en poängsumma på $4$.

Fallet $k = 4$: Om du får dra 4 kort från bordet är det bästa sättet: efter att ha dragit det första kortet med poäng lika med $4$, välj att slänga ett kort med poäng lika med $4$, så att kort med poängen $6, 3, 9, 6, 3$ blir kvar på handen. Vid 2:a dragningen har kortet poäng lika med $6$; det bästa sättet är att slänga båda (2) korten med poäng lika med $3$, så att korten på handen blir $6, 9, 6, 6$. Vid 3:e dragningen har kortet poäng lika med $9$; välj att slänga båda (2) korten med poäng lika med $9$. Och när du drar det sista kortet med poäng lika med $6$ kan du slänga 4 kort med poäng lika med $6$. Detta slängande leder till att inga kort finns kvar på handen, vilket betyder att kortens poängsumma är $0$.

Din uppgift (Your Task)

Hitta ”den minsta poängsumman för korten som finns kvar på handen” efter avslutade $k$ rundor för $k = 1, 2, 3, \ldots, M$.

Denna uppgift har ett programmeringsformat som skiljer sig från det vanliga formatet och som kommer att användas under den faktiska tävlingen. Se slutet av denna uppgift för information om hur det används.

Implementationsdetaljer

Du ska skriva följande funktion:

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

med följande parametrar:

• $A$ är en array med längd $N$ som anger numren på korten på handen i början.
• $B$ är en array med längd $M$ som anger numren på korten som ligger på bordet, ordnade från vänster till höger.
• Funktionen ska returnera en array $C$ med längd $M$ som representerar den minsta möjliga poängsumman för korten på handen efter $k$ rundor för $k = 1, 2, 3, \ldots, M$.

Till exempel, om $A = [6, 3, 9, 6, 3]$ och $B = [4, 6, 9, 6]$ ska funktionen returnera arrayen $[19, 10, 4, 0]$.

Begränsningar

• $1 \le N, M \le 10^6$
• $1 \le A[i] \le 10^9$ för varje $i$ där $1 \le i \le N$
• $1 \le B[i] \le 10^9$ för varje $i$ där $1 \le i \le M$

Deluppgifter

Anmärkning

Programmeringsinstruktioner

För denna uppgift skiljer sig sättet att skriva programmet och skicka in det till bedömningssystemet (Grader) från det allmänna programmeringsformatet där den tävlande måste skriva delen som läser indata och delen som skriver ut utdata. I denna uppgift behöver den tävlande endast skriva den nödvändiga beräkningsdelen i den angivna funktionen. De olika indata kommer att vara tillgängliga via funktionens parametrar, och beräkningsresultaten ska också returneras via funktionen, utan att den tävlande behöver skriva någon del för inläsning av indata eller utskrift av utdata.

Den tävlande kommer att få flera filer enligt följande; den tävlande ska endast ändra en enda fil enligt uppgiftens anvisningar och skicka in denna fil till systemet:

• grader.cpp är huvudfilen som ansvarar för att läsa in indata och skriva ut utdata.
• kang.cpp är filen där den tävlande ska skriva programmets beräkningar och är den fil som den tävlande skickar in till systemet (i filen kang.cpp får det inte finnas någon funktion main(), men andra funktioner är tillåtna).
• run_cpp.sh är filen som den tävlande kan anropa för att köra hela programmet.
• compile_cpp.sh är filen som den tävlande kan anropa för att kompilera programmet.

Den tävlande får en .zip-fil som kan laddas ner från systemet; när denna fil packas upp (extract) finns alla 4 filerna i den. Den tävlande bör använda en textredigerare (text editor) eller en IDE för att redigera filen kang.cpp och kompilera eller köra programmet genom att anropa compile_cpp.sh eller run_cpp.sh.

När den tävlande anropar filen run_cpp.sh för att köra programmet kommer programmet att fungera enligt vad som anges i filen grader.cpp, där avsnittet ”Beskrivning av grader-filen” förklarar hur denna fil fungerar.