23635번 - 산타로부터의 선물

문제

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$번째 아이가 받은 선물의 기쁨 수치의 합을 $k_i$라고 하자.

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

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

입력

첫 번째 줄에 아이의 수를 나타내는 정수 $K$와 선물의 개수를 나타내는 정수 $N$이 주어진다.

두 번째 줄에는 각 선물의 기쁨 수치를 나타내는 $N$개의 정수$A_i$($i$번 선물의 기쁨 수치)가 공백으로 구분되어 순서대로 주어진다.

• 1ドル < K \leq 10$
• $K \leq N \leq 202,000$
• 1ドル ≤ A_i < 500,000$ (1ドル \leq i \leq N$)
• $\sum_{i=1}^{N}A_i \leq 500,000$

출력

$\sum_{i=1}^{K} {(k_i - \min_{j=1}^{K}(k_j))}$의 최솟값을 출력한다.

제한

힌트