17439번 - 꽃집

수학이니 과학이니, 컴퓨터니 사람이니, ……. 복잡하고 슬픈 세상에 신물이 난 남서는 새해가 되고 추위가 가실 즈음, 도시를 떠나 조용한 마을에 꽃집을 열었다.

남서는 처음엔 N송이의 꽃을 가격순으로 일렬로 늘어놓았다. 그런데 개점 소식을 듣고 꽃집에 놀러 온 남서의 친구 끄드흐가 남서에게 이렇게 조언했다.

"꽃이 N송이나 되니까 둘러보기가 너무 힘들어. 꽃다발로 묶는 게 어때?"

생각해보니 그랬다. N송이는 너무 많지 않은가! 그래서 남서는 꽃을 꽃다발로 묶어 정리하기로 했다. 남서는 몇 가지 조건을 세웠다.

• 각각의 꽃을 꼭 한 번씩 사용한다. 따라서 모든 꽃은 반드시 단 하나의 꽃다발에 속한다.
• 꽃다발을 만들 땐 가격순으로 진열된 현재 상태에서 인접한 꽃끼리만 묶는다. 즉, 각 꽃다발을 구성하는 꽃의 원래 위치는 연속한 구간을 이루어야 한다.
• 꽃다발의 가격은, 그 꽃다발에 묶인 꽃의 가격의 합에, 묶인 꽃의 개수를 곱한 값이다. (그 이유는, 이해하긴 어렵지만 영업 비밀이라고 한다.)
• 꽃다발은 총 K개 이하로 만든다. (손님들이 보기 편하게 진열하기 위함이라고 한다.)

이제 꽃다발을 어떻게 만들지 고민하던 남서는, 모든 꽃다발의 가격의 합이 꽃다발을 만드는 방법에 따라 달라질 수 있다는 사실을 깨달았다. 남서는 착하기 때문에 모든 꽃다발의 가격의 합이 최소가 되도록 꽃다발을 만들려고 한다.

N개의 꽃의 가격이 진열된 순서대로 주어질 때, K개 이하의 꽃다발을 만들어 모든 꽃다발의 가격의 합을 최소화했을 때의 그 합을 구하는 프로그램을 작성하시오.

첫 번째 줄에 양의 정수 N과 K가 주어진다. (1 ≤ N, K ≤ 50,000)

두 번째 줄에 꽃의 가격을 의미하는 N개의 양의 정수 v_i가 띄어쓰기를 사이에 두고 주어진다. (1 ≤ v_i ≤ 50,000)

주어지는 수열 v_i는 단조 증가 수열임이 보장된다. 즉, 1 ≤ j ≤ N-1를 만족하는 모든 j에 대해, v_j ≤ v_j+1임이 보장된다.

첫 번째 줄에, K개 이하의 꽃다발을 만들 때 모든 꽃다발의 가격의 합의 최솟값을 출력한다.

첫 번째 예제에서는 다음과 같이 세 개의 꽃다발을 만들면 된다.

• (1, 1)로 하나,
• (5, 6)로 또 하나,
• (9)로 하나.

꽃다발의 가격은 각각 4, 22, 9이므로 총 가격은 4 + 22 + 9 = 35이다. 꽃다발의 가격의 합을 이보다 작게 만들 수 있는 방법은 없다.