* أجزاء الإنتاج
Problem
المؤسسة "Auto-2010" تنتج محركات للسيارات ذات الشهرة العالمية. يتكون المحرك من أجزاء n بالضبط ، مرقمة من 1 إلى n ، والجزء الذي يحمل الرقم i مصنوع بالثواني pi. تفاصيل مؤسسة "Auto-2010" هو أنه يمكن تصنيع جزء محرك واحد فقط في كل مرة. تتطلب بعض الأجزاء إنتاج مجموعة مسبقة الصنع من الأجزاء الأخرى.
مدير عام "أوتو 2010" تعيين مهمة طموحة للمؤسسة و [مدش] ؛ لإنتاج الجزء الأول في أقصر وقت لتقديمه في المعرض.
مطلوب كتابة برنامج ، بالنظر إلى تبعيات ترتيب الإنتاج بين الأجزاء ، سيجد أقصر وقت يمكن فيه إنتاج رقم الجزء 1.
إدخال
يحتوي السطر الأول من ملف الإدخال على الرقم n (1 & le؛ & nbsp؛ n & le؛ & nbsp؛ 100000) & mdash؛ عدد أجزاء المحرك. يحتوي السطر الثاني على n أعداد صحيحة موجبة p 1 ، p 2 ، p n ، والتي تحدد وقت التصنيع لكل جزء بالثواني. لا يتجاوز وقت صياغة كل جزء 10 9 ثوانٍ.
يصف كل سطر من الأسطر n التالية من ملف الإدخال خصائص إنتاج الأجزاء. هنا يحتوي السطر الأول على عدد الأجزاء k المطلوبة لإنتاج رقم الجزء i ، بالإضافة إلى أرقامها. لا توجد أرقام مكررة للجزء في السطر الأول. مجموع كل الأرقام k i لا يتجاوز 200000.
من المعروف أنه لا توجد تبعيات دورية في إنتاج الأجزاء.
بصمة
يجب أن يحتوي السطر الأول من ملف الإخراج على رقمين: الحد الأدنى للوقت (بالثواني) المطلوب لإنتاج رقم الجزء 1 في أقرب وقت ممكن وعدد k للأجزاء التي يجب إنتاجها لهذا الغرض. في السطر الثاني ، تحتاج إلى طباعة أرقام مفصولة بمسافات و [مدش] ؛ أرقام الأجزاء بالترتيب الذي يجب إنتاجها به لإنتاج الجزء رقم 1 في أسرع وقت ممكن.
نبسب ؛
<الجسم>
| إدخال
| الإخراج
|
3
100200300
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
|