Problem
شرکت "Auto-2010" موتورهایی برای خودروهای معروف دنیا تولید می کند. موتور دقیقاً از n قسمت تشکیل شده است که از 1 تا n شماره گذاری شده اند، در حالی که قطعه با شماره i در ثانیه پی ساخته می شود. مشخصات شرکت "Auto-2010" این است که تنها یک قطعه موتور را می توان در یک زمان در آنجا ساخت. برخی از قطعات برای تولید به مجموعه ای پیش ساخته از قطعات دیگر نیاز دارند.
مدیر کل "Auto-2010" یک وظیفه بلندپروازانه برای شرکت تنظیم کنید — برای تولید قطعه شماره 1 در کمترین زمان برای ارائه در نمایشگاه.
نوشتن برنامه ای الزامی است که با توجه به وابستگی های ترتیب تولید بین قطعات، کوتاه ترین زمان ممکن برای تولید قطعه شماره 1 را پیدا کند.
ورودی
خط اول فایل ورودی حاوی عدد n (1≤ n ≤ 100000) — تعداد قطعات موتور خط دوم شامل n عدد صحیح مثبت p
1، p
2، p
n است که زمان ساخت هر قطعه را بر حسب ثانیه تعریف می‌کند. زمان ساخت هر قسمت از 10
9 ثانیه تجاوز نمی کند.
هر یک از n خط بعدی فایل ورودی ویژگی های تولید قطعات را شرح می دهد. در اینجا خط i-ام شامل تعداد قطعات ki مورد نیاز برای تولید قطعه شماره i و همچنین تعداد آنها است. هیچ شماره قطعه تکراری در خط i وجود ندارد. مجموع همه اعداد k
i از 200000 تجاوز نمی کند.
مشخص است که هیچ وابستگی چرخه ای در تولید قطعات وجود ندارد.
حصر
خط اول فایل خروجی باید شامل دو عدد باشد: حداقل زمان (بر حسب ثانیه) لازم برای تولید قطعه شماره 1 در اسرع وقت و تعداد k قطعاتی که برای این کار باید تولید شوند. در خط دوم باید k اعداد جدا شده با فاصله — شماره قطعه به ترتیبی که باید تولید شود تا در اسرع وقت قطعه شماره 1 تولید شود.
<بدن>
| ورودی |
خروجی |
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
|