Problem
Entreprise "Auto-2010" produit des moteurs pour des voitures de renommée mondiale. Le moteur est constitué d'exactement n parties, numérotées de 1 à n, tandis que la partie portant le numéro i est réalisée en pi secondes. Les spécificités de l'entreprise "Auto-2010" est qu'une seule pièce de moteur peut y être fabriquée à la fois. Certaines pièces nécessitent un ensemble préfabriqué d'autres pièces pour être produites.
Directeur général de "Auto-2010" définir une tâche ambitieuse pour l'entreprise — produire la pièce numéro 1 dans les plus brefs délais pour la présenter au salon.
Il est nécessaire d'écrire un programme qui, compte tenu des dépendances de l'ordre de production entre les pièces, trouvera le temps le plus court dans lequel il est possible de produire la pièce numéro 1.
Entrée
La première ligne du fichier d'entrée contient le nombre n (1≤ n ≤ 100000) — nombre de pièces du moteur. La deuxième ligne contient n entiers positifs p
1, p
2, p
n, qui définissent le temps de fabrication de chaque pièce en secondes. Le temps de fabrication de chaque pièce ne dépasse pas 10
9 secondes.
Chacune des n lignes suivantes du fichier d'entrée décrit les caractéristiques de la fabrication des pièces. Ici, la ième ligne contient le nombre de pièces ki requises pour produire la pièce numéro i, ainsi que leurs numéros. Il n'y a pas de numéros de pièce en double dans la ième ligne. La somme de tous les nombres k
i ne dépasse pas 200 000.
On sait qu'il n'y a pas de dépendances cycliques dans la production de pièces.
Mentions légales
La première ligne du fichier de sortie doit contenir deux nombres : le temps minimum (en secondes) requis pour produire la pièce numéro 1 dès que possible et le nombre k de pièces qui doivent être produites pour cela. Dans la deuxième ligne, vous devez imprimer k nombres séparés par des espaces — les numéros de pièce dans l'ordre dans lequel ils doivent être produits afin de produire le numéro de pièce 1 dès que possible.
| Entrée |
Sortie |
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
|