Cutting Sticks

인기도:B(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:2(1~4)

나무막대를 여러 조각으로 잘라야 한다. 절단 분야에서 가장 뛰어난 것으로 알려진 ACM(Analog Cutting Machinery)이라는 회사에서는 자를막대의 길이에 따라 요금을 부과한다. 그리고 톱의 구조상 한 번에 하나씩만 자를 수 있다.
절단 순서에 따라 요금이 달라진다는 것은 그리 어렵지 않게 알 수 있다. 예를 들어 10미터짜리 막대를 한 쪽 끝으로부터 2, 4, 7미터 위치에서 자르는 경우를 생각해보자. 자를 수 있는 방법은 매우 다양하다. 처음에 2미터 위치에서 자르고 그 다음에 4미터 위치, 마지막으로 7미터 위치에서 자를 수도 있다. 이렇게 하면 요금은 10+8+6=24가 된다. 첫번째 막대는 10미터였고, 그 다음 막대는 8미터였고, 마지막 막대는 6미터였기 때문이다. 하지만 일단 4미터 지점에서 자르고 2미터 지점에서 자른 다음 마지막에 7미터 지점에서 자르면 요금이 10+4+6=20이 되므로, 앞에서 잘랐던 방법으로 하는 것보다 요금을 줄일 수 있다. 어떤 막대가 주어졌을 때, 최소 절단 요금을 구하는 프로그램을 만들어보자.

여러 테스트 케이스가 입력된다. 각 테스트 케이스의 첫째 줄에는 자를 막대의 길이를 나타내는 양의 정수 l이 입력된다. l은 1,000 미만이라고 가정하자. 그 다음 줄에는 잘라야 할 횟수 n (n < 50)이 입력된다.
그 다음 줄에는 n개의 양의 정수 Ci ( 0 < Ci < l) 가 입력되는데, 이 숫자들은 막대를 잘라야 할 위치를 나타내며, 오름차순으로 입력된다.(같은 정수가 두 번 입력되는 일은 없다.)
l의 값으로 0이 입력되면 입력이 종료된 것을 의미한다.

각 막대를 자르는 데 드는 최소 비용을 아래 예에 나와있는 것과 같은 식으로 출력한다.

~cpp 
100
3
25 50 75
10
4
4 5 7 8
0

~cpp 
The minimum cutting is 200.
The minimum cutting is 22.

작성자	사용언어	개발시간	코드
문보창	C++	2일	CuttingSticks/문보창
김상섭	C++	3년	CuttingSticks/김상섭
하기웅	C++	몇일	CuttingSticks/하기웅

----
문제분류 / 경시대회준비반