Qarşıda sizi uzun bir avtomobil səyahəti gözləyir. Təəssüf ki, avtomobilinizdə yalnız maqnitofon var və ən yaxşı musiqilər CD-lərə yazılır. Sizdə N dəqiqə ifa müddəti olan boş lentiniz var. Lentə yazmaq üçün mahnıları elə seçmək lazımdır ki, onun üzərində istifadə olunmayan yer minimal olsun.
Fərziyyələr:
CD-dəki treklərin sayı 100-dan çox deyil
heç bir trek N dəqiqədən çox çəkmir
hər trekin uzunluğu tam ədəd kimi ifadə edilir
N həm də tam ədəddir (0≤N≤200).
Proqram CD-də olduğu kimi treklərin eyni sırasını qoruyarkən lentə yazılan treklərin mümkün olan maksimum uzunluğunu tapmalıdır.
Giriş çoxlu sətirlərdən ibarətdir. Hər bir sətirdə əvvəlcə N rəqəmi, sonra treklərin sayı və hər trekin müddəti var. Bütün nömrələr boşluqlarla ayrılır. Məsələn, giriş məlumatlarının birinci sətirində birinci verilən N=5, sonra treklərin sayı s=3, birinci trekin müddəti 1 dəqiqə, ikinci - 3 dəqiqə, və sonuncu - 4 dəqiqə.
"sum:" sətrini və ardınca qeydin müddətini çap edin.