НОВ  БЪЛГАРСКИ  УНИВЕРСИТЕТ
Департамент Информатика
XVIIІ РЕПУБЛИКАНСКА СТУДЕНТСКА ОЛИМПИАДА ПО ПРОГРАМИРАНЕ
13 - 14 май 2006 г.

    Задача A. Разрязване на прът 
    Метален прът трябва да бъде нарязан на няколко парчета. Цената в лева за извършване на едно отрязване е равна на дължината на рязания прът в метри. В даден момент може да бъде правен само един разрез. Различни стратегии за нарязване водят до различна цена. 
    Например да разгледаме прът с дължина 10 метра, който трябва да бъде нарязан във 2-рия, 4-тия и 7-мия метър. Бихме могли да извършим това като направим най-напред разрез в 2-ри метър, после в 4-ти метър и накрая 7-ми метър. Това струва 10 + 8 + 6 = 24 лева. Друг подход може да бъде да отрежем първо в 4-ти метър, после във 2-ри и в 7-ми метър. Сега цената е 10 + 4 + 6 = 20 лева. 
    Да се напише програма A, която пресмята минималната цена на нарязване на прът с дадена дължина. 
    Вход. 
    Входът съдържа данни за няколко пръта. Първият ред за всеки тестов случай съдържа положително число l < 105, което представлява дължината на металния прът, който трябва да бъде нарязан. Вторият ред съдъжа положително число n < 104, задаващо броя на разрезите за този прът. Следващият ред съдържа n положителни числа ci, (0 < ci < l), задаващи местата, в които трябва да бъдат направени разрезите. Прочитането на стойност l = 0 означава край на входа. 
    Изход. 
    Отпечатва се минималната цена на нарязване на съответния прът по зададения формат в примера. 
	Примерен вход. 
100 
3 
25 50 75 
10
4 
4 5 7 8 
0 	Изход. 
The minimum price is 200. 
The minimum price is 22.