Un gioco di carte, rinomato come una prova d'intelligenza, si chiama «Kang». In questo gioco, ogni carta ha un punteggio pari a un intero positivo. All'inizio, ricevi $N$ carte da tenere in mano, e ci sono altre $M$ carte posate scoperte sul tavolo, disposte da sinistra a destra. Puoi vedere i punteggi di tutte le carte, sia quelle ricevute in mano sia quelle sul tavolo. Successivamente, puoi pescare carte dal tavolo per altri $k$ turni, pescando una carta alla volta da sinistra a destra. Dopo aver pescato una carta in ciascun turno, puoi scartare carte dalla tua mano 1 volta, scegliendo un qualsiasi numero di carte in mano che abbiano lo stesso punteggio. Devi pianificare il tuo gioco in modo che, dopo aver pescato carte dal tavolo e scartato carte dalla mano per $k$ turni completi, le carte rimanenti in mano abbiano la somma dei punteggi minima possibile.

Considera il seguente esempio:

Se all'inizio hai cinque carte con punteggi $6, 3, 9, 6, 3$, e le carte sul tavolo hanno punteggi da sinistra a destra pari a $4, 6, 9, 6$:

Caso $k = 1$: Se puoi pescare solo 1 carta dal tavolo, quando peschi la prima carta, i punteggi delle carte che hai saranno $6, 3, 9, 6, 3, 4$. Poi puoi scegliere di scartare carte con lo stesso punteggio 1 volta. Il modo migliore è scegliere di scartare 2 carte con punteggio uguale a $6$, in modo che la somma dei punteggi delle carte rimanenti sia minima e pari a $3 + 9 + 3 + 4 = 19$.

Caso $k = 2$: Se puoi pescare 2 carte dal tavolo, il modo migliore è: dopo aver pescato la prima carta con punteggio uguale a $4$, scegli di scartare una carta con punteggio uguale a $9$. Le carte rimanenti in mano hanno punteggi $6, 3, 6, 3, 4$. Poi, quando peschi la 2ª carta con punteggio uguale a $6$, potrai scartare 3 carte con punteggio uguale a $6$, facendo sì che le carte rimanenti abbiano la somma dei punteggi minima pari a $3 + 3 + 4 = 10$.

Caso $k = 3$: Se puoi pescare 3 carte dal tavolo, il modo migliore è: quando peschi la prima carta, i punteggi delle carte in mano saranno $6, 3, 9, 6, 3, 4$. Poi scegli di scartare carte con lo stesso punteggio 1 volta; il modo migliore è scartare entrambe le 2 carte con punteggio uguale a $3$, lasciando in mano le carte $6, 9, 6, 4$. Successivamente, quando peschi la 2ª carta con punteggio uguale a $6$, potrai scartare 3 carte con punteggio uguale a $6$, lasciando in mano le carte $9, 4$. E quando peschi per la 3ª volta una carta con punteggio uguale a $9$, potrai scartare entrambe le 2 carte con punteggio uguale a $9$, facendo sì che le carte rimanenti abbiano una somma dei punteggi pari a $4$.

Caso $k = 4$: Se puoi pescare 4 carte dal tavolo, il modo migliore è: dopo aver pescato la prima carta con punteggio uguale a $4$, scegli di scartare una carta con punteggio uguale a $4$, lasciando in mano carte con punteggi $6, 3, 9, 6, 3$. Poi, alla 2ª pescata, la carta ha punteggio uguale a $6$; il modo migliore è scartare entrambe le 2 carte con punteggio uguale a $3$, lasciando in mano le carte $6, 9, 6, 6$. Alla 3ª pescata, la carta ha punteggio uguale a $9$; scegli di scartare entrambe le 2 carte con punteggio uguale a $9$. E pescando l'ultima carta con punteggio uguale a $6$, potrai scartare 4 carte con punteggio uguale a $6$. Questo scarto fa sì che non rimangano carte in mano, il che significa che la somma dei punteggi delle carte è $0$.

Il tuo compito (Your Task)

Trova la «somma minima dei punteggi delle carte rimanenti in mano» dopo aver completato $k$ turni, per $k = 1, 2, 3, \ldots, M$.

Questo problema ha un formato di programmazione diverso dal formato normale, che verrà utilizzato nella gara effettiva. Si prega di consultare la fine di questo testo per le istruzioni sull'utilizzo.

Dettagli di implementazione

Devi implementare la seguente funzione:

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

con i seguenti parametri:

• $A$ è un array di lunghezza $N$ che specifica i numeri delle carte in mano all'inizio.
• $B$ è un array di lunghezza $M$ che specifica i numeri delle carte posate sul tavolo, ordinate da sinistra a destra.
• La funzione deve restituire un array $C$ di lunghezza $M$ che rappresenta la minima somma possibile dei punteggi delle carte in mano dopo $k$ turni, per $k = 1, 2, 3, \ldots, M$.

Ad esempio, se $A = [6, 3, 9, 6, 3]$ e $B = [4, 6, 9, 6]$, la funzione deve restituire l'array $[19, 10, 4, 0]$.

Limitazioni

• $1 \le N, M \le 10^6$
• $1 \le A[i] \le 10^9$ per ogni $i$ tale che $1 \le i \le N$
• $1 \le B[i] \le 10^9$ per ogni $i$ tale che $1 \le i \le M$

Sottoproblemi

Note

Istruzioni di programmazione

Per questo problema, il metodo per scrivere il programma e inviarlo al sistema di valutazione (Grader) differisce dal formato generale in cui il concorrente deve scrivere la parte di lettura dell'input e la parte di stampa dell'output. In questo problema, il concorrente deve scrivere soltanto la parte di calcolo necessaria all'interno della funzione specificata. I vari dati di input saranno accessibili tramite i parametri della funzione, e anche i risultati del calcolo dovranno essere restituiti tramite la funzione, senza che il concorrente debba scrivere la parte di lettura dell'input né la parte di stampa dell'output.

Il concorrente riceverà diversi file come segue, e dovrà modificare un solo file come specificato dal problema e inviare tale file al sistema:

• grader.cpp è il file principale responsabile della lettura dell'input e della scrittura dell'output.
• kang.cpp è il file in cui il concorrente deve scrivere i vari calcoli del programma ed è il file che il concorrente invia al sistema (nel file kang.cpp è vietato avere la funzione main(), ma possono esserci altre funzioni).
• run_cpp.sh è il file che il concorrente può eseguire per avviare l'intero programma.
• compile_cpp.sh è il file che il concorrente può eseguire per compilare il programma.

Il concorrente riceverà un file .zip scaricabile dal sistema; una volta estratto, conterrà tutti e 4 i file. Il concorrente dovrebbe usare un editor di testo o un IDE per modificare il file kang.cpp e compilare o eseguire il programma richiamando compile_cpp.sh o run_cpp.sh.

Quando il concorrente esegue il file run_cpp.sh per avviare il programma, il programma funzionerà come specificato nel file grader.cpp, la cui sezione «Descrizione del file grader» spiega il funzionamento di tale file.