eolymp
bolt
Try our new interface for solving problems
Məsələlər

Jedayev akademiyası

Jedayev akademiyası

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Jeday olmaq üçün bir çox nəzəri və praktik vərdişlərə sahib olmaq lazımdır. Jedayev akademiyasında, əlbəttə ki, əgər qabiliyyətiniz vardırsa, hər bir lazım olan şeyi öyrənmək olar.

Akademiyanın yeni tələbəsi Fil çox qabiliyyətlidir və fərdi məşğul olur. O öz cədvəlini özü sərbəst tuta bilər. Fil çox maraqlı şəxsdir, buna görə də bütün vaxtını təhsilə sərf edir. Fil yalnız akademiyanın bir binasından digərinə gedərkən və ya yataqxanadan binaların birinə gedərkən oxumur.

Akademiya iki binadan ibarətdir. Bunlardan birində nəzəri, digərində isə praktik biliklər öyrədilir. Bir binadan digərinə getmək a dəqiqəyə başa gəlir. İstənilən biliyin öyrədilməsi tam b dəqiqə tələb edir. Başlanğıcda Fil yataqxanada olur. Yataqxanadan hər bir binaya getmək a dəqiqəyə başa gəlir.

Aydındır ki, bilikləri ixtiyari ardıcıllıqda öyrənmək olar. Məsələn, işıq qılıncı əldə etməzdən əvvəl optikanın əsaslarını və əlbəyaxa döyüş sənətini öyrənmək lazımdır. Fil iş qrafiki hazırlayarkən bunu nəzərə almalıdır.

Fil tez bir zamanda jeday olmaq istəyir, lakin bunun üçün o bütün bilikləri əldə etməlidir. Təhsilə başlamazdan əvvəl o nə qədər müddətə bütün bilikləri əldə edəcəyini bilmək istəyir. Bunu təyin etməkdə ona kömək edin. Təhsilini bitirdikdən sonra Fill birbaşa şərlə mübarizə aparmağa yollanacaq, onun yataqxanaya qayıtmasına ehtiyac yoxdur.

Giriş verilənləri

Giriş faylının ilk sətrində akademiyada əldə ediləcək biliklərin sayını ifadə edən n (1n10^5) tam ədədi verilir. Bütün biliklər 1-dən n-ə qədər nömrələnir.

Növbəti n sətirdə hər bir biliyin öyrənilməsi üçün tələblər şərh edilir. Başlanğıcda bu sətirlərdən i-sində 1 və ya 2 ədəd yazılır, bu i-ci biliyi hansı binada öyrənməyin mümkün olduğunu bildirir. Sonra i biliyini öyrənmək üçün biliklərin sayını ifadə edən k ədədi verilir. Bütün biliklər üzrə ədədlərin k cəminin 10^5-i aşmadığına zəmanət verilir.

Növbəti sətirdə bir binadan digər binaya və ya yataqxanadan binaya getmək üçün sərf olunan vaxtın dəqiqə ilə qiymətini ifadə edən a tam ədədi və bir biliyin öyrənilməsi üçün lazım olan vaxtı ifadə edən b tam ədədi verilir (1a, b10^4).

Bütün biliklərin öyrənilməsi üçün elə ardıcıllıq mövcuddur ki, növbəti biliyin öyrənilməsi zamanı bunun üçün lazım olan bütün alt biliklər əvvəlcədən öyrənilmiş olur.

Çıxış verilənləri

Çıxış faylının yeganə sətrində Filinin jeday olması üçün tələb olunan minimal zamanı verin.

Nümunə

Giriş verilənləri #1
6
1 3 3 4 5
2 1 4
2 2 5 6
1 1 6
1 0
1 0
15 40
Çıxış verilənləri #1
285
Mənbə XIII All-Russian Olympiad schoolchildren team programming