DVD

Petyanın yeni bir kompüter oyunu var. Dostları ona boş DVD disklər gətirib oyunu köçürməsini xahiş etdilər. Petya hər şeyi M+1 saniyə ərzində hazır edəcəyinə söz verdi. Amma ilk diski yazmağa başlayanda evində təmir işləri olduğunu və elektrik kəsintiləri olacağını xatırladı, bu səbəbdən vaxtında bitirə bilməyəcəyini düşündü. Petya məsuliyyətli olduğuna görə dostları vaxtında çatdıra bilməsə, inciyəcəklər.

Oyun tam olaraq bir DVD diskinin bütün yerini tutur. Petya'nın StrangeDVD sürücüsü $4\text{X}$, $8\text{X}$ və $16\text{X}$ sürətlərində yazma dəstəkləyir, burada $X$-in mənası fərqli ola bilər — $4\text{X}$ StrangeDVD digər sürücülərdəki ilə uyğun olmaya bilər. Fərz edək ki, tray dərhal açılıb bağlanır və Petya diski çıxarıb tez birini yerləşdirə bilir, yəni vaxt yalnız yazma müddətinə sərf olunur. StrangeDVD multisessiya dəstəkləmir, yəni hər disk bir dəfə də fasiləsiz yazılmalıdır.

$16\text{X}$-də yazılanda keyfiyyət $1$; $8\text{X}$-də $2$; $4\text{X}$-də $3$ olur. Petya diskləri elə yazmalıdır ki, ümumi keyfiyyət maksimum olsun və əgər variantlar çoxdursa, vaxt minimal olsun.

Elektrik kəsintiləri razılaşdırılmayıb və üst-üstə düşə bilər. Əgər yeni kəsinti başlayanda elektrik artıq gedibsə, onun əlavə təsiri yoxdur. Məsələn, $1$-ci saniyədən $10$-a, $5$-dən $20$-yə və $15$-dən $30$-a kimi üç kəsinti varsa, $1$-də işıq sönəcək, $5$-də heç nə dəyişməyəcək (çünki işıq artıq sönüb), $11$-də yanacaq, $15$-də yenə sönəcək, $31$-də isə yenidən yanacaq. Heç vaxt iki briqada eyni vaxtda işıq söndürmür. Sayım $0$-cı saniyədən başlayır, ümumi M+1 saniyə (0, 1, …, M).