Maldição das Moiras
As Moiras, deusas do destino, escreveram o destino dos mortais em uma fita mística composta por $N$ fragmentos. Cada fragmento contém um número inteiro que representa uma dor futura para o herói que tentar enfrentar seu destino.
O herói, no entanto, recebeu a bênção de Atena, que lhe permite remover certos fragmentos da fita e assim evitar algumas dessas dores. Mas há duas regras:
-
Ele não pode remover dois fragmentos adjacentes, pois isso rompe o fio do destino e causa caos cósmico.
-
Ele é obrigado a remover até $K$ fragmentos.
A tarefa do herói é minimizar a dor total (a soma dos fragmentos que permanecem na fita) após remover até $K$ fragmentos, respeitando as regras exigidas.
Input
A primeira linha contém dois inteiros $N$ e $K$ $(0 \le K \le 100, 1 \le N \le 10^5)$, o número de fragmentos e a quantidade de fragmentos que o herói deve remover.
A segunda linha contém $N$ inteiros $A_1, A_2, ..., A_n$ $(0 \le A_i \le 10^9)$, representando a dor de cada fragmento.
Output
Um único inteiro: a menor soma possível da dor total restante, após remover até K fragmentos respeitando as regras.
10 3 0 0 6 10 9 0 0 1 0 0
10
15 3 4 4 8 10 9 3 8 7 9 8 6 3 3 6 1
62