*Piezas de producción
Problem
Empresa "Auto-2010" produce motores para automóviles de fama mundial. El motor consta exactamente de n partes, numeradas del 1 al n, mientras que la parte con el número i se fabrica en pi segundos. Los detalles de la empresa "Auto-2010" es que allí solo se puede fabricar una pieza de motor a la vez. Algunas partes requieren un conjunto prefabricado de otras partes para ser producidas.
Director General de "Auto-2010" establecer una tarea ambiciosa para la empresa — producir la pieza número 1 en el menor tiempo posible para presentarla en la exposición.
Se requiere escribir un programa que, dadas las dependencias del orden de producción entre piezas, encuentre el menor tiempo en el que sea posible producir la pieza número 1.
Entrada
La primera línea del archivo de entrada contiene el número n (1≤ n ≤ 100000) — número de partes del motor. La segunda línea contiene n enteros positivos p1, p2, pn, que definen el tiempo de fabricación de cada pieza en segundos. El tiempo para fabricar cada pieza no supera los 109 segundos.
Cada una de las siguientes n líneas del archivo de entrada describe las características de la producción de piezas. Aquí, la i-ésima línea contiene el número de partes ki requeridas para producir el número de parte i, así como sus números. No hay números de pieza duplicados en la i-ésima línea. La suma de todos los números ki no excede 200000.
Se sabe que no existen dependencias cíclicas en la producción de piezas.
Impresión
La primera línea del archivo de salida debe contener dos números: el tiempo mínimo (en segundos) requerido para producir la parte número 1 lo antes posible y el número k de partes que se deben producir para esto. En la segunda línea, debe imprimir k números separados por espacios — números de pieza en el orden en que deben producirse para producir el número de pieza 1 lo antes posible.
| Entrada |
Salida |
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
|