CD

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\le N\le 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ş verilənləri

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ə.

Çıxış verilənləri

"sum:" sətrini və ardınca qeydin müddətini çap edin.

Nümunələr