Анюта və Google
Onuncu sinif şagirdi Anya mikrobiologiyaya maraq göstərir və yeni virus növləri haqqında hesabat hazırlayır. Məlum olduğu kimi, Google insanların ən yaxşı dostudur, buna görə də Anya onunla dostluq edir. Hesabat hazırlayarkən o, axtarış sistemində çox çalışdı və yaxşı məlumat topladı. Anya aşağıdakı kimi işləyirdi:
Əvvəlcə o, Google-da axtarış sorğusu daxil etdi və ona kifayət qədər maraqlı görünən bir neçə link aldı.
Anya bilir ki, əgər tapılmış və siyahısına daxil edilmiş səhifələrdən birini yükləsə, orada digər səhifələrə keçidlər ola bilər. Bu səhifələri də yükləmək olar. O, məhz belə hərəkət edərək onu maraqlandıran bütün səhifələri yüklədi.
Anya yükləməni təkrarladı, ta ki onun siyahısında tam olaraq n müxtəlif səhifə olana qədər.
Lakin demək olar ki, hesabat hazır olan anda Anya'nın sevimli pişiyi Murzik yenidən kabeli dişləyib qırdı və İnternet kəsildi! Bu o deməkdir ki, son lazım olan səhifə yüklənmədi. Təəssüf ki, Anya bütün səhifələri 1, 2, ..., n nömrələri ilə siyahıya daxil etdi, lakin İnternetdə səhifələrin tam ünvanlarını yazmadı. İndi Anya bu son səhifəni tapıb yükləmək məcburiyyətindədir.
Günahkar Murzik mətbəxə bağlandı və buna çox incidi. Kabel dəyişdirildi. İndi Anya Google-da axtarış sorğusundan istifadə etdiyi mənbələrin siyahısındakı son səhifəyə qədər yenidən keçmək istəyir, yəni Murzik'in oxumasına mane olduğu səhifəni yükləmək istəyir. Hal-hazırda Anya'nın səhifələrin siyahısı var və hər səhifə üçün aşağıdakı məlumatlar məlumdur:
səhifənin baytlarla həcmi,
verilmiş səhifədən keçilə bilən səhifələrin siyahısı.
Anya çox maraqlıdır - lazım olan səhifəyə keçidlər vasitəsilə çatmaq üçün minimum neçə bayt yükləməlidir? Ona bu problemi həll etməyə kömək edin!
Giriş məlumatları
Birinci sətir siyahıdakı İnternet səhifələrinin sayını n ehtiva edir. Daha sonra n sətir gəlir, i-ci sətir p[i] - səhifənin baytlarla həcmi və m[i] - i-ci səhifədən keçilə bilən səhifələrin sayını ehtiva edir. Daha sonra həmin sətirdə m[i] tam ədədlər - i-ci səhifədən keçilə bilən səhifələrin nömrələri var. Bu siyahıdakı ilk səhifə Google-dur. Siyahıdakı son səhifə Anya'nın yolunu tapmaq istədiyi səhifədir. Səhifələr 1-dən başlayaraq nömrələnir. n dəyəri 100-ü keçmir. Hər səhifənin həcmi sıfıra bərabər deyil və 1 meqabaytı keçmir, baytlarla verilir.
Çıxış məlumatları
Bir ədəd çıxarın - birinci səhifədən sonuncu səhifəyə keçidlər vasitəsilə çatmaq üçün yüklənməli olan minimum baytların sayı. Belə bir yolun həmişə mövcud olduğu təmin edilir.