Cow Routing II#11186
Stanca del freddo inverno nella sua fattoria, la mucca Bessie decide di volare verso una destinazione più calda per una vacanza. Purtroppo, scopre che soltanto una compagnia aerea, la Air Bovinia, è disposta a vendere biglietti alle mucche, e che questi biglietti sono in qualche modo complicati.
Air Bovinia possiede aerei, ciascuno dei quali vola lungo una specifica "rotta" composta da due o più città. Per esempio, un aereo potrebbe volare lungo una rotta che parte dalla città , poi vola verso la città , poi verso la città , e infine verso la città . Nessuna città compare più di una volta su una rotta.
Se Bessie sceglie di utilizzare una rotta, può salire sull'aereo in qualsiasi città lungo la rotta e poi scendere in qualsiasi città che appaia successivamente sulla rotta. Non ha bisogno di salire nella prima città né di scendere nell'ultima città. Ogni rotta ha un costo fisso, che Bessie deve pagare se utilizza una qualsiasi parte di quella rotta, indipendentemente da quante città visiti lungo di essa. Inoltre, Bessie può utilizzare ciascuna rotta al massimo una volta (cioè, non può utilizzare una parte di una rotta e successivamente utilizzare un'altra parte della stessa rotta).
Bessie vuole trovare il modo più economico per viaggiare dalla sua fattoria, situata nella città , fino alla sua destinazione tropicale, situata nella città . Poiché non vuole avere a che fare con un itinerario complicato, desidera utilizzare al massimo due rotte. Aiutala a determinare il costo totale minimo che deve pagare.
La prima riga contiene , e n~(1 \le n \le 500).
Le successive righe descrivono le rotte disponibili, con due righe per rotta. La prima riga contiene il costo di utilizzo della rotta (un intero da a ) e il numero di città lungo la rotta (un intero da a ). La seconda riga contiene l'elenco delle città nell'ordine in cui appaiono lungo la rotta. Ogni città è identificata da un intero nell'intervallo da a .
Stampa il costo minimo di un itinerario che utilizza al massimo due rotte e che permette a Bessie di viaggiare dalla città alla città . Se non esiste un tale itinerario, stampa .
Utilizza la rotta per viaggiare dalla città alla città , e poi utilizza la rotta per viaggiare dalla città alla città .
Esempio 1
Nota che l'unica differenza tra questo problema e il precedente problema Bronze è che qui Bessie può utilizzare fino a due rotte, mentre nel problema precedente poteva utilizzarne solo una.