Ruota della fortuna

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

Descrizione del problema

Giorgio gestisce una ruota della fortuna a premi.

La ruota è suddivisa in $N$ spicchi uguali, numerati da $0$ a $N-1$, in senso orario. Lo spicchio $i$ corrisponde a un premio di un certo valore $V_i$.

I premi vengono assegnati in questo modo. Dopo aver comprato il biglietto, ognuno dei giocatori si posiziona in corrispondenza di uno spicchio a sua scelta, e non si muove più. Quando tutti i giocatori sono in posizione, la ruota viene fatta girare. Quando finalmente la ruota si ferma, ciascun giocatore vince un premio in base al valore del nuovo spicchio che si trova davanti a lui.

Giorgio ha taroccato il meccanismo della ruota per fermarla quando gli conviene di più. Ti viene dato il valore dei premi per ogni spicchio, e il numero $G_i$ di giocatori posizionati davanti a ciascuno spicchio $i$. Aiuta Giorgio a calcolare la somma totale dei premi che dovrà pagare, fermando la ruota in modo che questa somma sia minima!

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 $3$ righe:

• la prima riga contiene l'intero $N$;
• la seconda riga contiene il valore dei premi $V_0, \, \dots, \, V_{N-1}$ di ciascuno spicchio;
• la terza riga contiene il numero di giocatori $G_0, \, \dots, \, G_{N-1}$ che si sono posizionati in corrispondenza di ciascuno spicchio.

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

dove t è il numero del caso di test (a partire da $1$) e il valore x è somma totale dei premi minima.

Assunzioni

• $T = 13$, nei file di input che scaricherai saranno presenti esattamente $13$ casi di test.
• $2 \le N \le 1000$.
• $0 \le V_i \le 1000$ per $i = 0, \, \dots, \, N - 1$.
• $0 \le G_i \le 1000$ per $i = 0, \, \dots, \, N - 1$.

Note

• La ruota può solo fermarsi ruotata esattamente di un numero intero di spicchi rispetto alla posizione iniziale.
• Se due o più giocatori si posizionano sullo stesso spicchio, NON si dividono il premio. Bensì, ciascuno di loro vince un premio pari all'intero valore dello spicchio.

Esempi di input/output

---

Input:

3

5
7 2 5 3 4
1 0 0 1 0

5
7 2 5 3 4
2 4 1 3 7

5
7 2 5 3 4
3 8 1 3 0

---

Output:

Case #1: 5
Case #2: 61
Case #3: 51

---

Spiegazione

In tutti e tre i casi la ruota ha $N = 5$ spicchi, con premi di valore $7$ euro, $2$ euro, $5$ euro, $3$ euro e $4$ euro.

Nel primo caso d'esempio, ci sono solo due giocatori. La somma minima dei premi è $5$ euro, e si ottiene fermando la ruota ruotata di $2$ spicchi in senso orario. In questo modo il primo giocatore riceverà un premio di $3$ euro e il secondo un premio di $2$ euro.

Nel secondo caso d'esempio, la somma minima dei premi è $61$ euro, e si ottiene fermando la ruota ruotata di $3$ spicchi in senso orario. (Quindi $2$ giocatori riceveranno un premio da $5$ euro, $4$ da $3$ euro, $1$ da $4$ euro, $3$ da $7$ euro, e $7$ da $2$ euro. La somma totale dei premi in euro è data da $2 \cdot 5 + 4 \cdot 3 + 1 \cdot 4 + 3 \cdot 7 + 7 \cdot 2 = 61$.)

Nel terzo caso d'esempio, la somma minima dei premi è $51$ euro, e si ottiene fermando la ruota esattamente nella posizione di partenza.