La mostra di Mojito

Per aiutarti con questo task, abbiamo preparato delle tracce di soluzione, che includono solo le parti di lettura dell'input e scrittura dell'output (da tastiera e su schermo). Puoi decidere se leggere/scrivere su file decommentando le opportune righe di codice.

• Scarica la traccia in C: mostra.c
• Scarica la traccia in C++: mostra.cpp
• Scarica la traccia in Python: mostra.py
• Scarica la traccia in Rust: mostra.rs

---

Descrizione del problema

Mojito, il cagnolino di Monica, terrà finalmente una mostra dei fantastici reperti che negli anni ha ritrovato nel suo giardino! Data l'importanza dell'evento, si sono create due lunghe file. Nella prima si sono assiepati $N$ turisti, ciascuno con un grado di preparazione $V[i]$. Nella seconda si sono accalcati $M$ volontari della scuola d'arte, che si offrono di guidare i turisti attraverso i reperti, ciascuno con un grado di preparazione $G[i]$.

Per l'accesso alla mostra dei turisti sono disponibili due tipi di biglietti: il biglietto senza guida al costo di 1 euro, e il biglietto con guida al costo di 2 euro. I volontari invece non pagano mai, che gli venga assegnato un turista oppure no. La grande calca impedisce di riordinare le persone in fila, ma è comunque possibile decidere il modo con cui far entrare le persone: individualmente da una delle due file, oppure abbinati dalle due file. È sempre possibile far entrare le persone individualmente, ma per mantenere alta la reputazione della mostra, è possibile abbinare un turista di preparazione $V[i]$ con una guida di preparazione $G[j]$ solo se la guida è più preparata del turista, ovvero se $G[j] > V[i]$. In caso contrario, il turista si troverebbe a spiegare i dettagli dell'arte di Mojito alla guida, uno smacco troppo grande per il museo!

Per ottenere il massimo profitto possibile, è importante abbinare bene le guide ai turisti, decidendo quali guide e turisti far entrare individualmente, e quali invece abbinare tra loro. Quanto può guadagnare al massimo la mostra dai biglietti, decidendo con cura l'assegnamento di guide ai turisti?

Dati di input

La prima riga del file di input contiene un intero $T$, il numero di casi di test. Seguono $T$ casi di test, numerati da $1$ a $T$. Ogni caso di test è preceduto da una riga vuota.

Ciascun caso di test è composto da $3$ righe: la prima contiene i due numeri interi $N$ ed $M$, rispettivamente il numero di turisti e il numero di volontari. La riga successiva contiene gli $N$ interi $V[i]$, i gradi di preparazione dei turisti. La terza riga contiene gli $M$ interi $G[i]$, i gradi di preparazione dei volontari.

Dati di output

Il file di output deve contenere la risposta ai casi di test che sei riuscito a risolvere. Per ogni caso di test che hai risolto, il file di output deve contenere una riga con la dicitura

Case #t: s

dove t è il numero del caso di test (a partire da $1$) e il valore s è il massimo guadagno che è possibile ottenere in questo caso di test.

Assunzioni

• $T=21$, nei file di input che scaricherai saranno presenti esattamente $21$ casi di test.
• $1 \le N,M \le 1000$.
• $0 \le V[i],G[i] \le 10^6$.

Esempi di input/output

---

Input:

4

2 5
2 2
1 1 7 2 9

5 3
1 2 3 4 5
3 3 3

3 1
8 6 7
20

2 2
5 1
2 6

---

Output:

Case #1: 4
Case #2: 7
Case #3: 4
Case #4: 3

---

Spiegazione

Nel primo caso d'esempio sono presenti 2 visitatori e 5 guide. Una soluzione ottima è la seguente:

• Il primo visitatore entra con la terza guida, per un guadagno di 2;
• Il secondo visitatore entra con l'ultima guida, per un guadagno di 2;
• Il ricavo totale è $2+2=4$.

Notiamo che non è possibile assegnare la prima, la seconda e la quarta guida a nessun turista, perchè nessuna di queste è abbastanza preparata. L'immagine seguente rappresenta la soluzione ottima:

---

Nel secondo caso d'esempio possiamo comportarci nel seguente modo:

• Facciamo entrare il primo visitatore con la prima guida, guadagnando 2;
• Facciamo entrare il secondo visitatore con la seconda guida, guadagnando di nuovo 2;
• Facciamo entrare da soli i rimanenti tre visitatori, perchè l'unica guida rimasta non è abbastanza preparata.

In questo modo guadagniamo $2+2+1+1+1=7$ euro, che è il massimo possibile.

---

Nel terzo caso d'esempio l'unica guida disponibile è così preparata da poter accompagnare qualsiasi turista. Possiamo, ad esempio, far entrare insieme la guida e il primo turista, ottenendo $2+1+1=4$ euro.

---

Nel quarto caso d'esempio la soluzione ottima è 3, ed è ottenibile in tre modi:

• Possiamo far entrare il primo turista con la seconda guida e il secondo turista da solo, oppure
• Possiamo far entrare il primo turista da solo e il secondo con la prima guida, oppure
• Possiamo far entrare il primo turista da solo e il secondo con la seconda guida.

Nota che non è possibile cambiare l'ordine delle persone, e in particolare non possiamo far entrare la prima guida col secondo turista e il primo turista con la seconda guida, che farebbe guadagnare 4 euro.

Di seguito una delle soluzioni ottime: