문자열 자르기

시간 제한2초메모리 제한512 MB

요약

길이 N인 문자열에서 잘라야 할 위치들이 주어질 때, 길이 L인 조각을 자르는 비용이 L일 때 모든 절단을 마치는 최소 총비용을 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 구간
정답자: 아직 제출이 없습니다

문제

길이가 N인 문자열을 두 조각으로 자르는 데 드는 비용은 N이다.

잘라야 하는 위치가 주어졌을 때, 모든 위치에서 문자열을 자르는 데 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

예를 들어 첫 문자를 1번이라 할 때 3번, 8번, 10번 문자 바로 뒤에서 잘라야 한다고 하자. 문자열이 thisisastringofchars이면 자를 자리를 |로 표시한 모습은 thi|sisas|tr|ingofchars이다.

왼쪽부터 차례대로 자르면 비용은 49이다.

thisisastringofchars     (문자열)
thi sisastringofchars    (비용 20)
thi sisas tringofchars   (비용 17)
thi sisas tr ingofchars  (비용 12)
                         합계 49

오른쪽부터 차례대로 자르면 비용은 38이다.

thisisastringofchars     (문자열)
thisisastr ingofchars    (비용 20)
thisisas tr ingofchars   (비용 10)
thi sisas tr ingofchars  (비용 8)
                         합계 38

자르는 순서는 마음대로 정한다. 주어진 위치를 모두 자르는 데 드는 비용의 최솟값을 구하시오.

입력

첫째 줄에 문자열의 길이 N ( $2 \le N \le 10^7$ )과 잘라야 하는 위치의 수 M ( $1 \le M \le 1000$ , $M < N$ )이 공백으로 구분되어 주어진다.

둘째 줄에 잘라야 하는 위치 M개가 공백으로 구분되어 증가하는 순서로 주어진다. 각 위치는 서로 다른 $1$ 이상 $N-1$ 이하의 정수이고, 그 번호의 문자 바로 뒤에서 문자열을 자른다는 뜻이다.

출력

주어진 위치를 모두 자르는 데 드는 비용의 최솟값을 첫째 줄에 출력한다.

예제2

예제 1
입력
```
20 3
3 8 10
```
예상 출력
```
37
```
예제 2
입력
```
20 4
2 3 8 10
```
예상 출력
```
40
```