Problem
Empresa "Auto-2010" produz motores para carros mundialmente famosos. O motor consiste em exatamente n peças, numeradas de 1 a n, enquanto a peça com o número i é feita em pi segundos. As especificidades da empresa "Auto-2010" é que apenas uma peça do motor pode ser fabricada lá por vez. Algumas peças requerem um conjunto pré-fabricado de outras peças para serem produzidas.
Diretor Geral da "Auto-2010" definir uma tarefa ambiciosa para a empresa — produzir a peça número 1 no menor tempo possível para apresentá-la na exposição.
É necessário escrever um programa que, dadas as dependências da ordem de produção entre as peças, encontre o menor tempo em que é possível produzir a peça número 1.
Entrada
A primeira linha do arquivo de entrada contém o número n (1≤ n ≤ 100000) — número de peças do motor. A segunda linha contém n inteiros positivos p
1, p
2, p
n, que definem o tempo de fabricação de cada peça em segundos. O tempo para fabricar cada peça não excede 10
9 segundos.
Cada uma das próximas n linhas do arquivo de entrada descreve as características da produção de peças. Aqui, a i-ésima linha contém o número de peças ki necessárias para produzir a peça número i, bem como seus números. Não há números de peça duplicados na i-ésima linha. A soma de todos os números k
i não excede 200000.
Sabe-se que não existem dependências cíclicas na produção de peças.
Impressão
A primeira linha do arquivo de saída deve conter dois números: o tempo mínimo (em segundos) necessário para produzir a peça número 1 o mais rápido possível e o número k de peças que precisam ser produzidas para isso. Na segunda linha, você precisa imprimir k números separados por espaços — números de peça na ordem em que devem ser produzidos para produzir o número de peça 1 o mais rápido possível.
| Entrada |
Saída |
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
|