시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB28151365.000%

문제

2021년에도 크리스마스가 찾아온다!

선물을 어떻게 나눠줄 지 고민하던 산타는 아이들에게 번호를 매기고 선물에도 번호를 매겨서 연속한 선물 번호를 묶어서 주기로 했다. 선물을 받지 못한 아이는 실망하므로 모든 아이들이 최소 하나 이상의 선물을 받아야 한다.

선물을 나눠줄 때는 1번 선물 부터 시작하여 몇 개를 묶고, 그 다음 선물 부터 몇 개를 묶고, 이것을 반복해서 줘야 한다. 또한 한 아이는 한 묶음의 선물만 받을 수 있다. 하지만 모든 선물을 나눠 줄 필요는 없다.

예를 들면, 아이 2명이 있고 선물이 5개가 있을 때 선물을 나눠주는 경우로 다음과 같은 예가 있다. [1, 2-3], [1-2, 3-4], [1-3, 4-5], [1-4, 5]

아래와 같은 예시로 선물을 줄 수는 없다. [1-2, 4-5], [2-4, 5]

불가능한 예시의 첫 번째 예시는 선물을 준 뒤 그 다음 선물부터 줘야한다는 규칙을 지키지 않았고 두 번째 예시는 1번 선물부터 주지 않았다.

각 선물에는 받았을 때 얻는 기쁨이 수치로 매겨져 있다. i번째 아이가 받은 선물의 기쁨 수치 합을 ki라고 하자.

산타는 $\sum_{i=1}^{K} {(k_i - min(k))}$을 최소화 하고 싶어한다. 이 때 min(k)는 모든 아이가 받은 선물의 기쁨 수치 합 중 가장 작은 값을 의미한다.

선물의 수가 너무 많아서 계산하기 어려워진 산타는 당신에게 이 값을 계산하는 프로그램을 만들어 달라고 의뢰했다. 산타를 위해 이 값을 구해주자!

입력

첫 번째 줄에 아이 명 수K(1 < K ≤ 10)와 선물 개수 N(K ≤ N ≤ 202,000)이 주어진다. 두 번째 줄에는 N개의 정수가 공백으로 구분되어 주어진다.

N개의 정수 중 i번째 수 ai(1 ≤ ai < 500,000)는 i번째 선물의 기쁨 수치를 나타낸다. ai의 합은 500,000을 넘지 않는다.

출력

$\sum_{i=1}^{K} {(k_i - min(k))}$의 최소값을 출력한다.

예제 입력 1

3 5
1 2 3 4 5

예제 출력 1

1

3명의 아이가 있다. [1-2, 3, 4]로 묶으면 각 합은[3, 3, 4]가 되어 min(k) = 3이므로 전체 답은 1이 된다.

예제 입력 2

3 5
3 1 4 2 2

예제 출력 2

0

[1-2, 3, 4-5]로 묶으면 각 합은[4, 4, 4]가 되어 min(k) = 4이므로 전체 답은 0이 된다.

예제 입력 3

3 6
21604 95462 60009 79876 82038 95514

예제 출력 3

76924

출처

University > 경북대학교 > 2021 Goricon I번