SuperLuigi Speedrun

Attenzione: Questo task ha un tempo limite di 10 minuti per l'invio della soluzione. Una volta richiesto un input, il timer partirà in automatico, e dopo la scadenza non sarà più possibile inviare una soluzione per quell'input. È sempre possibile richiedere un nuovo input, per cui non preoccuparti se il timer scade: dovrai semplicemente richiedere e scaricare un nuovo input.

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: superluigi.c
• Scarica la traccia in C++: superluigi.cpp
• Scarica la traccia in C#: superluigi.cs
• Scarica la traccia in Go: superluigi.go
• Scarica la traccia in JavaScript: superluigi.html
• Scarica la traccia in Java: superluigi.java
• Scarica la traccia in Pascal: superluigi.pas
• Scarica la traccia in Python: superluigi.py
• Scarica la traccia in VisualBasic: superluigi.vb

Descrizione del problema

Luca ha comprato il nuovissimo videogioco SuperLuigi. Luigi, il protagonista del videogioco, in ogni livello deve superare $N$ piloni numerati da $0$ ad $N-1$. Su ogni pilone ci sono $M$ piattaforme su cui Luigi può saltare. La piattaforma più in basso dell'$i$-esimo pilone si trova ad $H_i$ metri dal suolo e le rimanenti $M-1$ piattaforme del pilone si trovano ciascuna $D_i$ metri sopra la piattaforma sottostante. Le piattaforme dell'$i$-esimo pilone sono quindi collocate alle altezze $H_i,H_i+D_i,H_i+2 \cdot D_i, \ldots, H_i+(M-1)\cdot D_i$. Quindi la piattaforma numero $j$, con $0 \le j < M$, sul pilone numero $i$, con $0 \le i < N$, si troverà ad $H_i + D_i \cdot j$ metri di altezza rispetto al suolo. Luigi deve raggiungere una qualsiasi piattaforma del pilone $N-1$ partendo da terra, ad altezza zero, subito prima del pilone $0$. Inizialmente deve quindi saltare su una qualunque piattaforma del pilone $0$, per poi spostarsi di pilone in pilone.

Per ogni pilone $i$, con $0 \le i < N-1$, Luigi può saltare da ogni piattaforma del pilone $i$ a una qualsiasi piattaforma del pilone $i+1$. Luca non vuole solo completare il livello, ma vuole metterci anche il minor tempo possibile. Per saltare da un punto ad altezza $h$ ad un punto di altezza $k$ Luigi impiega $|h - k|$ (valore assoluto di $h-k$) secondi. Il tempo totale impiegato per completare un livello è quindi la somma dei tempi impiegati in ogni salto. Quanti secondi servono, al minimo, per completare il livello?

Formato 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 come segue:

• una riga contenente i due interi $N$, $M$.
• una riga contenente gli $N$ interi $H_{0}, \, \ldots, \, H_{N-1}$.
• una riga contenente gli $N$ interi $D_{0}, \, \ldots, \, D_{N-1}$.

Formato 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 #test: tempo"

dove $\mathtt{test}$ è il numero del caso di test (a partire da $1$) e l'intero $\mathtt{tempo}$ è la riposta al test.

Assunzioni

• $T = 10$, nei file di input che scaricherai saranno presenti esattamente $10$ casi di test.
• $2 \le N \le 1\,000$
• $2 \le M \le 10\,000$
• $0 \le H_i \le 10\,000$ per ogni $i = 0, \, \dots, \, N-1$.
• $0 \le D_i \le 10\,000$ per ogni $i = 0, \, \dots, \, N-1$.
• nei primi $2$ casi di test vale inoltre che $M = 2$.

Esempi di input/output

---

Input:

3

2 2
1 1
2 3

3 3
9 0 8 
8 2 15 

5 2
6 10 7 1 4 
4 17 10 14 1

---

Output:

Case #1: 1
Case #2: 18
Case #3: 22

---

Spiegazione

Nel primo caso d'esempio Luca può far saltare Luigi da terra fino alla piattaforma $0$ sul pilone $0$ ad altezza $1$ impiegandoci $1$ secondo. Poi può far saltare Luigi sulla piattaforma $0$ sul pilone $1$ ad altezza $1$ impiegandoci $0$ secondi. La riposta dunque sarà $1$ e Luca non può fare di meglio.

Nel secondo caso d'esempio Luca può far fare le seguenti mosse a Luigi:

• Saltare sulla piattaforma ad altezza $9$ sul pilone $0$ mettendoci $9$ secondi.
• Saltare sulla piattaforma più in alto sul pilone $1$ ad altezza $4$ mettendoci $5$ secondi.
• Saltare sulla piattaforma ad altezza $8$ sull'ultimo pilone mettendoci $4$ secondi. in totale Luca ci mette $18$ secondi a completare il livello.

Nel terzo caso d'esempio, il livello è come segue.