Module: टोपोलॉजिकल सॉर्ट

Problem

उद्यम "ऑटो-2010" विश्व प्रसिद्ध कारों के लिए इंजन बनाती है। इंजन में ठीक n भाग होते हैं, जिनकी संख्या 1 से n तक होती है, और संख्या i वाले भाग को pi सेकंड में बनाया जाता है। उद्यम "ऑटो-2010" की विशिष्टता यह है कि एक समय में केवल एक इंजन भाग का निर्माण किया जा सकता है। कुछ हिस्सों को बनाने के लिए दूसरे हिस्सों के प्रीफैब्रिकेटेड सेट की जरूरत होती है।

"ऑटो-2010" के जनरल डायरेक्टर उद्यम के लिए एक महत्वाकांक्षी कार्य निर्धारित करें — प्रदर्शनी में प्रस्तुत करने के लिए कम से कम समय में भाग संख्या 1 का निर्माण करने के लिए।

यह एक प्रोग्राम लिखने के लिए आवश्यक है कि, भागों के बीच उत्पादन के क्रम की निर्भरता को देखते हुए, कम से कम समय मिलेगा जिसमें भाग संख्या 1 का उत्पादन संभव है।

इनपुट
इनपुट फ़ाइल की पहली पंक्ति में संख्या n (1≤ n ≤ 100000) — इंजन भागों की संख्या। दूसरी पंक्ति में n धनात्मक पूर्णांक p₁, p₂, p_n हैं, जो सेकंड में प्रत्येक भाग के निर्माण समय को परिभाषित करते हैं। प्रत्येक भाग को तैयार करने का समय 10⁹ सेकंड से अधिक नहीं है।

इनपुट फ़ाइल की अगली n पंक्तियों में से प्रत्येक भागों के उत्पादन की विशेषताओं का वर्णन करती है। यहां i-th लाइन में भाग संख्या i, साथ ही साथ उनकी संख्या का उत्पादन करने के लिए आवश्यक भागों की संख्या शामिल है। i-th लाइन में कोई डुप्लीकेट पार्ट नंबर नहीं हैं। सभी संख्याओं का योग k_i 200000 से अधिक नहीं है।

यह ज्ञात है कि भागों के उत्पादन में कोई चक्रीय निर्भरता नहीं है।

छाप
आउटपुट फ़ाइल की पहली पंक्ति में दो संख्याएँ होनी चाहिए: न्यूनतम समय (सेकंड में) जितनी जल्दी हो सके भाग संख्या 1 का उत्पादन करने के लिए आवश्यक है और इसके लिए आवश्यक भागों की संख्या k। दूसरी पंक्ति में आपको k स्पेस-सेपरेटेड नंबर — जितनी जल्दी हो सके भाग संख्या 1 का उत्पादन करने के लिए भाग संख्याएं जिस क्रम में उन्हें उत्पादित किया जाना चाहिए।
  <तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स"> <शरीर> इनपुट आउटपुट 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