꽃집

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

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

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

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

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

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

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

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

두 번째 줄에 꽃의 가격을 나타내는 $N$개의 양의 정수 $v_i$가 띄어쓰기를 사이에 두고 주어진다. ($1 \le v_i \le 50,000$)

주어지는 수열 $v_i$는 단조 증가 수열임이 보장된다. 즉, $1 \le j \le N-1$을 만족하는 모든 $j$에 대해 $v_j \le v_{j+1}$이다.

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

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

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

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