Problem
Kurumsal "Oto-2010" dünyaca ünlü otomobiller için motorlar üretiyor. Motor tam olarak 1'den n'ye kadar numaralandırılmış n parçadan oluşuyor ve i numaralı parça pi saniyede yapılıyor. "Auto-2010" girişiminin özellikleri orada bir seferde yalnızca bir motor parçası üretilebilmesidir. Bazı parçaların üretilmesi için prefabrik bir dizi başka parça gerekir.
"Auto-2010" Genel Müdürü kuruluş için iddialı bir görev belirleyin — 1 numaralı parçayı en kısa sürede üreterek fuarda sergilemek.
Parçalar arasındaki üretim sırasının bağımlılıkları göz önüne alındığında, 1 numaralı parçanın üretilebileceği en kısa süreyi bulan bir program yazmak gerekmektedir.
Girdi
Girdi dosyasının ilk satırı n (1≤ n ≤ 100000) — sayısını içerir. motor parçası sayısı İkinci satır, her bir parçanın üretim süresini saniye cinsinden tanımlayan n pozitif tamsayı p
1, p
2, p
n içerir. Her bir parçayı yapma süresi 10
9 saniyeyi geçmez.
Girdi dosyasının sonraki n satırının her biri, parça üretiminin özelliklerini açıklar. Burada i'inci satır, i numaralı parçayı üretmek için gereken ki parça sayısını ve bunların numaralarını içerir. i'nci satırda yinelenen parça numarası yok. Tüm sayıların k
i toplamı 200000'i geçmez.
Parça üretiminde döngüsel bağımlılıkların olmadığı bilinmektedir.
Künye
Çıktı dosyasının ilk satırı iki sayı içermelidir: 1 numaralı parçayı mümkün olan en kısa sürede üretmek için gereken minimum süre (saniye olarak) ve bunun için üretilmesi gereken parça sayısı k. İkinci satırda k boşlukla ayrılmış sayıları — 1 numaralı parçanın en kısa sürede üretilebilmesi için parça numaralarının üretilmeleri gereken sırayla.
| Giriş |
Çıktı |
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
|