Abzas
Abzasda müxtəlif hündürlükdə bloklar var (məsələn, adi sözlər və riyazi simvollar). Abzas uzundur, buna görə də onu sətirlərə bölmək lazımdır. Sətirin hündürlüyü, içindəki ən hündür blokun hündürlüyünə bərabərdir. Abzasın hündürlüyü isə bütün sətirlərin hündürlüklərinin cəminə bərabərdir. Hər bir sətirin uzunluğu, həmin sətirdəki blokların ümumi eninə bərabərdir (boşluqları nəzərə almaq lazım deyil). Blokun sətirdən sətirə keçməsi üçün bölünməsi mümkün deyil. Blokların ardıcıllığını dəyişmək olmaz. Abzasın hündürlüyünü minimum etmək üçün sətirlərə belə bir bölünmə tapmaq lazımdır. Hər bir blokun eni və hündürlüyü (w(i), h(i)) və sətirin maksimal icazə verilən uzunluğu TW giriş məlumatlarında verilir.
Giriş verilənləri
Birinci sətirdə iki ədəd yazılıb - TW (sətirin maksimal icazə verilən uzunluğu) və N (abzasdakı blokların sayı), burada 5 ≤ N ≤ 5000. Növbəti N sətirdə - hər biri iki ədəd (blokun eni və hündürlüyü).
Bütün ölçülər 10^6-dan böyük olmayan natural ədədlərdir. Bütün bloklar üçün w(i) ≤ TW təmin edilir.
Çıxış verilənləri
Birinci sətirdə abzasın minimal hündürlüyünü yazın. İkinci sətirdə abzası bölmək üçün lazım olan sətirlərin sayı M, və növbəti M sətirdə abzasın müvafiq sətirlərindəki blokların sayını yazın.