시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 63 13 8 22.857%

문제

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

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

예를 들어, 3, 8, 10번 (첫 문자: 1)의 다음 위치에서 문자열을 잘라야 하는 경우를 생각해보자. 즉, 문자열이 thisisastringofchars인 경우에, 3, 8, 10번 문자의 다음 위치를 |로 표시해보면 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 ≤ N ≤ 10,000,000)과 잘라야 하는 위치의 수 M (1 ≤ M ≤ 1000, M < N)이 주어진다.

둘째 줄에는 문자열을 잘라야 하는 위치가 주어진다.

출력

문자열을 입력으로 주어진대로 자르기 위해 필요한 비용의 최소값을 출력한다.

예제 입력

20 3
3 8 10

예제 출력

37

예제 입력 2

20 4
2 3 8 10

예제 출력 2

40

힌트

출처