Corsa ad ostacoli

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

Descrizione del problema

Monica ha deciso di portare Mojito ad una corsa ad ostacoli!

La corsa si svolge in un tracciato rettilineo lungo $L$ metri, e la partenza si trova all'inizio del tracciato nel punto $0$. Nel tracciato sono presenti $N$ ostacoli: ciascun ostacolo si trova a $X_i$ metri dalla partenza ed ha una difficoltà $P_i$, per cui superando tale ostacolo Mojito guadagna $P_i$ punti.

Per rendere la corsa più difficile, gli organizzatori hanno però deciso che ciascun ostacolo può essere attraversato solo in un breve intervallo. In particolare, l'$i$-esimo ostacolo appare dopo $S_i$ secondi dall'inizio della gara e scompare immediatamente dopo, quindi per poter superare l'ostacolo Mojito deve trovarsi esattamente nel punto $X_i$ all'instante $S_i$. Mojito può correre avanti e indietro nel tracciato oppure può stare fermo a rincorrersi la coda, purtroppo però è in grado di correre solo fino a $1$ metro al secondo.

La corsa dura esattamente $D$ secondi, al termine dei quali si sommano i punteggi degli ostacoli che Mojito è riuscito a superare. Mojito si è allenato duramente, ed è quindi in grado di superare tutti gli ostacoli che riesce a raggiungere in tempo senza difficoltà. Qual è il massimo numero di punti che Mojito riesce a totalizzare?

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 i tre interi $N$, $L$, $D$;
• le successive $N$ righe contengono ciascuna tre interi $X_i$, $P_i$ e $S_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: x

dove t è il numero del caso di test (a partire da $1$) e il valore x è il massimo punteggio che Mojito può totalizzare.

Assunzioni

• $T = 19$, nei file di input che scaricherai saranno presenti esattamente $19$ casi di test.
• $1 \le N \le 1000$.
• $1 \le L, D \le 10^9$.
• $0 \le X_i \le L$ per ogni $0 \le i \le N-1$.
• $0 \le P_i \le 10^6$ per ogni $0 \le i \le N-1$.
• $0 \le S_i \le S_{i+1} \le D$ per ogni $0 \le i \le N-2$.

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

• $L \le 100$.

Nei primi $6$ casi di test valgono, inoltre, le seguenti assunzioni aggiuntive:

• $N, D \le 100$.

Esempi di input/output

---

Input:

2

2 20 20
7 30 2
9 10 11

4 10 10
7 20 7
4 6 7
3 7 8
2 5 9

---

Output:

Case #1: 10
Case #2: 20

---

Spiegazione

Nel primo caso d'esempio Mojito non è in grado di raggiungere il primo ostacolo all'istante $2$ in quanto è troppo distante dalla partenza. Quindi, può solo prendere il secondo ostacolo guadagnando $10$ punti. Per farlo, per esempio, può correre fino al punto dove comparirà l'ostacolo, rincorrersi la coda sul posto per 2 secondi e all'istante $11$ superare l'ostacolo.

---

Nel secondo caso d'esempio Mojito può andare all'istante $7$ nel punto $4$ e poi spostarsi nei punti $3$ e $2$ prendendo gli ultimi $3$ ostacoli, oppure può andare all'istante $7$ nel punto $7$. La prima scelta permette a Mojito di guadagnare $6+7+5 = 18$ punti mentre la seconda scelta gli permette di guadagnare $20$ punti, la risposta è quindi $20$.