Նախատոնական եռուզեռ
Նոր Տարվա նախօրեին շատ գործ կա անելու։ Ամբողջ ընտանիքը լծվել է գործի։ Ամեն ինչը պետք է ավարտել, որքան հնարավոր է, շուտ։ Դրա համար պետք է ձգտել զուգահեռ մի քանի գործ անել։ Բայց, մյուս կողմից, գործերը պետք է անել որոշակի հերթականությամբ, օրինակ, պետք է գնալ խանութ առևտուր անել, հետո նոր սալաթ պատրաստել, բայց այդ ընթացքում ինչ-որ մեկը կարող է տանը մաքրության գործ անել։
Տրված է գործերի ցուցակը, գործերը համարակալված են -ից թվերով, հայտնի է յուրաքանչյուր գործ անելու տևողությունը, և թե տվյալ գործն անելու համար մինչ այդ որ համարի գործերը պետք է արված լինեն։ Պահանջվում է գտնել բոլոր գործերն ավարտելու համար մինիմալ հնարավոր ժամանակը։
Մուտքային տվյալներ
Առաջին տողում տրված է գործերի քանակը։ Հաջորդ տողերից յուրաքանչյուրում նկարագրվում է մեկ գործ։ Համարենք, որ գործերը համարակալված են -ից թվերով։ Այդ տողերից -րդում նախ տրվում է տվյալ գործն անելու համար անհրաժեշտ ժամանակը , ապա տրվում է մի թիվ, որը ցույց է տալիս այն գործերի քանակը, որոնք պետք է ավելի շուտ արվեն, քան -րդ գործը, դրան հաջորդում են այդ հատ գործերի համարները։
-րդ գործը կարող է կախված լինել միայն -ից գործերից։ Դա երաշխավորում է, որ փոխադարձ կախվածություն չլինի, այսինքն չլինի այնպես, որ գործը պետք է գործից շուտ արվի և հակառակը՝ -ը -ից շուտ արվի։
Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝ բոլոր գործերն ավարտելու համար հնարավոր մինիմալ ժամանակը։
Օրինակ
Մուտք | Ելք |
|---|---|
| |
Օրինակի պարզաբանումը․ գործ կա անելու։ -ին գործի տևողությունը է, այն ոչ մեկից կախված չէ։ -րդ գործի տևողությունը է, այն պետք է արվի -ին գործից հետո միայն, հետևաբար կավարտվի ժամանակի -րդ պահին։ -րդ գործի տևողությունը է, այն պետք է արվի -ին և -րդ գործերի ավարտից հետո, այսինքն կավարտվի ժամանակի -րդ պահին։ -րդ գործը կախված է միայն -րդ գործից, կավարտվի -րդ պահին։ -րդ գործը մնացած բոլոր գործերից անկախ է, կավարտվի -րդ պահին։ Հատևաբար, ժամանակի -րդ պահին բոլոր գործերն ավարտված կլինեն։
Constraints
Time limit: 1.6 seconds
Memory limit: 512 MB
Output limit: 1 MB