Impila le scatole

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: pile.c
• Scarica la traccia in C++: pile.cpp
• Scarica la traccia in Python: pile.py
• Scarica la traccia in Java: pile.java
• Scarica la traccia in C#: pile.cs
• Scarica la traccia in JavaScript: pile.html
• Scarica la traccia in JavaScript (Node.js): pile.js

Descrizione del problema

Mojito e i suoi amici sono a caccia di cibo nascosto nei più disparati angoli della casa di Monica!

In casa di Monica sono disponibili $N$ diverse scatole che è possibile utilizzare, e la scatola $i$-esima è rappresentata da un parallelepipedo i cui tre lati misurano $A_i$, $B_i$, $C_i$ metri.

I quadrupedi, in assenza di Monica, hanno deciso utilizzare le $N$ scatole a disposizione per raggiungere le più alte credenze in cui Monica ha nascosto del cibo! Per farlo, hanno intenzione di impilare tutte le scatole una sopra l'altra scegliendo, per ognuna di essa, il lato da utilizzare in altezza e sul quale saltare.

Le scatole saranno impilate appoggiando le facce scelte tra di loro, e l'altezza finale della pila di scatole così creata sarà la somma dei lati corrispondenti alle altezze delle scatole disposte.

Aiuta Mojito e i suoi amici a trovare l'altezza massima raggiungibile impilando le $N$ scatole a disposizione!

Nota: Quando si parla di cibo i cani sono maestri di agilità, e saranno in grado di impilare le scatole in qualsiasi configurazione sfidando la legge di gravità!

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.

Ogni caso di test è composto da $N+1$ righe:

• la prima riga contiene l'intero $N$;
• le successive $N$ righe contengono ciascuna tre interi $A_i$, $B_i$ e $C_i$.

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: h

dove t è il numero del caso di test (a partire da $1$) e il valore h è la massima altezza ottenibile impilando le $N$ scatole.

Assunzioni

• $T = 6$, nei file di input che scaricherai saranno presenti esattamente $6$ casi di test.
• $1 \le N \le 100$.
• $1 \le A_i, B_i, C_i \le 100$ per ogni $0 \le i \le N-1$.

Nei primi $2$ casi di test valgono le seguenti assunzioni aggiuntive:

• $A_i = B_i = C_i$ (tutte le scatole sono cubiche).

Esempi di input/output

---

Input:

2

2
2 3 4
2 2 2

3
1 3 7
4 2 1
3 9 5

---

Output:

Case #1: 6
Case #2: 20

---

Spiegazione

Nel primo caso d'esempio è possibile raggiungere l'altezza di $6$ metri impilando la prima scatola con altezza $4$ e la seconda scatola con altezza $2$.

Nel secondo caso d'esempio è possibile raggiungere l'altezza di $20$ metri impilando la prima scatola con altezza $7$, la seconda scatola con altezza $4$ e la terza scatola con altezza $9$.