Given an array with N elements you need to choose exactly K non-consecutive elements from it such that the sum of the elements will be minimum.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ K ≤ N
•  - 10⁹ ≤ a_i ≤ 10⁹

I know how to solve this in O(N·K) by using DP(i, m) =  minimum sum that can be obtained in prefix i taking exactly m elements.

Can it be done faster than that? Thanks beforehand.

EDIT: I had an idea that was do a binary search on the answer, let's say answer should be less or equal than x, then for a prefix i the values that m can take so that DP(i, m) ≤ x are consecutive so I transformed the DP to DP(i) =  range of the valid m values. But the problem with this is how to merge DP(i - 1) with DP(i - 2) in time.