*НОВ БЪЛГАРСКИ УНИВЕРСИТЕТ* *Департамент Информатика* 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 < 10^5 , което представлява дължината на металния прът, който трябва да бъде нарязан. Вторият ред съдъжа положително число n < 10^4 , задаващо броя на разрезите за този прът. Следващият ред съдържа n положителни числа c_i , (0 < c_i < 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.