Problem
Enterprise "Auto-2010" produces engines for world-famous cars. The engine consists of exactly n parts, numbered from 1 to n, and the part with number i is made in pi seconds. The specifics of the enterprise "Auto-2010" is that only one engine part can be manufactured there at a time. Some parts require a prefabricated set of other parts to be produced.
General Director of "Auto-2010" set an ambitious task for the enterprise — to produce part number 1 in the shortest time to present it at the exhibition.
It is required to write a program that, given the dependencies of the order of production between parts, will find the shortest time in which it is possible to produce part number 1.
Input
The first line of the input file contains the number n (1≤ n ≤ 100000) — number of engine parts. The second line contains n positive integers p
1, p
2, p
n, which define the manufacturing time of each part in seconds. The time to craft each part does not exceed 10
9 seconds.
Each of the next n lines of the input file describes the characteristics of the production of parts. Here the i-th line contains the number of parts ki required to produce part number i, as well as their numbers. There are no duplicate part numbers in the i-th line. The sum of all numbers k
i does not exceed 200000.
It is known that there are no cyclic dependencies in the production of parts.
Imprint
The first line of the output file should contain two numbers: the minimum time (in seconds) required to produce part number 1 as soon as possible and the number k of parts that need to be produced for this. In the second line you need to print k space-separated numbers — part numbers in the order in which they should be produced in order to produce part number 1 as soon as possible.
| Input |
Output |
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
|