환승 통로 건설

문제

한 지하철 노선에는 N개의 역이 일직선으로 늘어서 있다. 역은 한쪽 끝부터 1번, 2번, ..., N번으로 번호가 붙어 있고, i번 역과 i+1번 역 사이의 거리는 d_i이다. (1 ≤ i ≤ N-1) 이 노선과 나란히 달리는 다른 노선과의 환승을 위해 보조 통로를 정확히 K개 건설하려 한다. 보조 통로는 이웃한 두 역 i번과 i+1번 사이의 구간 하나를 골라 그 구간을 따라 짓는 것이며, 건설 비용은 그 구간의 거리 d_i와 같다. 한 역에는 통로 공사 장비를 둘 공간이 하나뿐이어서, 어떤 역도 두 개 이상의 통로에 속할 수 없다. 즉 고른 구간들은 서로 역을 공유하지 않아야 하며, 구간 i와 구간 i+1은 함께 고를 수 없다. 같은 구간을 두 번 고를 수도 없다. 입력에서 2K ≤ N이 보장되므로 항상 K개를 고를 수 있다. 고른 K개 구간의 거리 합이 최소가 되도록 할 때, 그 최솟값을 구하라. K가 0이면 답은 0이다.

입력

첫째 줄에 N과 K가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 0 ≤ K, 2K ≤ N) 둘째 줄에 N-1개의 정수 d_1, ..., d_{N-1}이 공백으로 구분되어 주어진다. (1 ≤ d_i ≤ 10^6) N이 1이면 둘째 줄은 비어 있거나 없을 수 있다.

출력

고른 구간 거리 합의 최솟값을 한 줄에 출력한다.

6 2
4 1 5 2 7

3

4 2
5 1 5

10

출처: Devin.KR 자체 제작