Problem
Impresa "Auto-2010" produce motori per auto di fama mondiale. Il motore è composto esattamente da n parti, numerate da 1 a n, e la parte con il numero i è realizzata in pi secondi. Le specifiche dell'impresa "Auto-2010" è che solo una parte del motore può essere prodotta lì alla volta. Alcune parti richiedono la produzione di un set prefabbricato di altre parti.
Direttore Generale di "Auto-2010" impostare un compito ambizioso per l'impresa — produrre la parte numero 1 nel minor tempo possibile per presentarla in fiera.
Si richiede di scrivere un programma che, date le dipendenze dell'ordine di produzione tra le parti, trovi il tempo più breve in cui è possibile produrre la parte numero 1.
Inserimento
La prima riga del file di input contiene il numero n (1≤ n ≤ 100000) — numero di parti del motore. La seconda riga contiene n numeri interi positivi p
1, p
2, p
n, che definiscono il tempo di produzione di ciascuna parte in secondi. Il tempo per creare ogni parte non supera i 10
9 secondi.
Ognuna delle successive n righe del file di input descrive le caratteristiche della produzione delle parti. Qui la riga i-esima contiene il numero di parti ki richieste per produrre la parte numero i, così come i loro numeri. Non ci sono numeri di parte duplicati nella riga i-esima. La somma di tutti i numeri k
i non supera 200000.
È noto che non ci sono dipendenze cicliche nella produzione di parti.
Impressum
La prima riga del file di output dovrebbe contenere due numeri: il tempo minimo (in secondi) richiesto per produrre la parte numero 1 il prima possibile e il numero k di parti che devono essere prodotte per questo. Nella seconda riga devi stampare k numeri separati da spazio — numeri di parte nell'ordine in cui dovrebbero essere prodotti al fine di produrre il numero di parte 1 il prima possibile.
| Input |
Uscita |
3
100 200 300
1 2
0
2 2 1
| 300 2
2 1
|
2
23
1 2
0 |
5 2
2 1
|
4
2 3 4 5
2 3 2
1 3
0
2 1 3
| 9 3
3 2 1
|