Il compleanno di Bessie#11172
In onore del compleanno di Bessie, Farmer John le ha permesso di pascolare liberamente in uno dei suoi migliori campi.
Il campo è composto da parcelle d'erba, numerate da , ciascuna con un valore unico di qualità dell'erba. Se Bessie mangia erba di qualità , ottiene unità di energia. Ogni parcella è collegata ad al massimo parcelle vicine tramite strade bidirezionali, e per spostarsi tra parcelle vicine Bessie spende unità di energia.
Bessie può scegliere qualsiasi parcella come posizione di partenza. Vuole pascolare finché non accumula la massima quantità possibile di energia.
Sfortunatamente, Bessie è una vacca capricciosa: dopo aver mangiato erba di una certa qualità, non mangerà mai più erba di qualità uguale o inferiore. Tuttavia, a Bessie non dispiace affatto passare per parcelle senza mangiare l'erba che vi cresce. Inoltre, potrebbe esserle conveniente passare per una parcella con erba di alta qualità senza mangiarla, per poi tornare più tardi a gustarsi quel delizioso spuntino.
Aiuta a determinare la massima quantità di energia che Bessie può accumulare.
Nella prima riga si trovano due numeri interi ed e~(1 \le n \le 1000, 1 \le e \le 10^6).
Ciascuna delle successive righe descrive una parcella d'erba. Ogni riga contiene due numeri interi e , dove q~(1 \le q \le 10^6) è la qualità dell'erba in quella parcella, e è il numero di parcelle vicine.
I successivi numeri interi in quella riga indicano i numeri delle parcelle vicine.
Stampa la massima quantità di energia che Bessie può accumulare.
Bessie inizia dalla parcella e ottiene unità di energia mangiando l'erba che cresce lì. Poi percorre la strada verso la parcella , perdendo unità di energia durante il tragitto. Rifiuta di mangiare l'erba di qualità inferiore nella parcella e torna alla parcella , perdendo altre unità di energia. Infine, mangia l'erba nella parcella , ottenendo unità di energia. In totale ottiene unità di energia.
Esempio 1