DVD
Petyanın yeni bir kompüter oyunu var. Dostları bunu öyrənəndə, ona boş DVD disklər gətirdilər və oyunu köçürməsini xahiş etdilər. Petya da hər şeyi M + 1 saniyə ərzində hazır edəcəyinə söz verdi. Lakin, Petyanın ilk diski yazmağa başladığı anda, evində təmir işlərinin aparıldığını və elektrik kəsilmələrinin baş verəcəyini xatırladı. Bu səbəbdən, bütün disklərə oyunu yazmağa vaxtı çatmaya bilər. Petyanın dostları onun çox məsuliyyətli olduğunu bildikləri üçün, əgər işini vaxtında bitirməsə, inciyəcəklər.
Oyun tamamilə bir DVD diskdəki boş yeri tutur. Petyanın StrangeDVD sürücüsü 4x, 8x və 16x sürətlərində yazmağı dəstəkləyir və bir qəribə xüsusiyyəti var: X dəyəri ümumi qəbul edilmiş standartdan fərqlidir, buna görə də StrangeDVD sürücüsündəki 4x sürəti və digər hər hansı bir sürücü ilə uyğun gəlməyə bilər. Fərz edək ki, sürücünün tepsisi dərhal açılır və bağlanır, və Petyanın diski sürücüdən çıxarıb sürücüyə qoyması da dərhal baş verir, yəni yalnız oyunun növbəti nüsxəsinin yazılmasına birbaşa vaxt sərf olunur. StrangeDVD sürücüsü multisessiyanı dəstəkləmir, buna görə də diskə yazma fasiləsiz aparılır.
16x sürətində yazıldıqda, yazılmış diskin keyfiyyət dəyəri 1, 8x sürətində — 2, 4x sürətində — 3 olur. Disklərin yazılmasına sərf olunan vaxtı tapmaq lazımdır ki, disklərin ümumi keyfiyyəti mümkün olan maksimum olsun, və əgər belə variantlar bir neçədirsə, sərf olunan vaxtın minimal olduğu variantı tapmaq lazımdır.
Elektrik kəsilmələri, bizdə adət olduğu kimi, işləyən briqadalar arasında razılaşdırılmır və bir-birinə üst-üstə düşə bilər. Əgər bu anda elektrik kəsilibsə və başqa bir briqada bu anda onu kəsməyi planlaşdırırdısa, təbii ki, bunu etməz. Yəni, əgər üç elektrik kəsilməsi planlaşdırılıbsa: 1-dən 10-cu saniyəyə qədər, 5-dən 20-ci və 15-dən 30-cu saniyəyə qədər, 1-ci saniyənin əvvəlində elektrik kəsildi, 5-ci saniyədə heç nə baş verməyəcək, çünki elektrik artıq kəsilib, 11-ci saniyənin əvvəlində elektrik qoşulacaq, 15-ci saniyənin əvvəlində kəsiləcək, 31-ci saniyənin əvvəlində qoşulacaq. Heç bir iki briqada eyni anda elektrik kəsmir. Zaman sayımı sıfırıncı saniyədən başlayır. Cəmi M + 1 saniyə (0, 1, ..., M).
Giriş verilənləri
Proqram klaviaturadan M (Petyanın sahib olduğu son saniyənin nömrəsi), N — yazılması lazım olan disk sayı, Q — 16x sürətində bir nüsxənin yazılması üçün vaxt (müvafiq olaraq 8x sürəti üçün bu vaxt 2Q, 4x sürəti üçün vaxt 4Q olacaq), K — elektrik kəsilmələrinin sayı oxuyur. Sonra K cüt ədəd P1, P2 - kəsilmənin başlanğıcı və sonu (saniyələrin nömrələri) gəlir. Bu cüt ədədlər xronoloji ardıcıllıqla yerləşdirilməmiş ola bilər, amma həmişə P1 ≤ P2. Bütün ədədlər boşluqlarla ayrılıb.
0 ≤ M, N, P1_{i}, p2_{i} ≤ 2 000 000 000, 1 ≤ Q ≤ 500 000 000 (və ya 1 ≤ 4Q ≤ 2 000 000 000), 0 ≤ K ≤ 10000.
Çıxış verilənləri
Proqram ekrana -1 çıxarır, əgər Petya bütün diskləri yazmağa vaxt tapmasa. Əgər vaxt tapsa, əvvəlcə Petyanın yazmağa sərf edəcəyi son saniyənin nömrəsini və boşluqla ayrılmış — yazma zamanı əldə edilən ümumi keyfiyyəti çıxarır.