Padurari

padurari

== include(page="template/taskheader" task_id="padurari") ==

De-a lungul unei şosele în linie dreaptă cresc $N$ copaci. $K$ pădurari au primit sarcina de a tăia o parte din copaci. Fiecare pădurar trebuie să taie exact $2$ copaci. Pădurarii se deplasează cu maşina până la primul copac pe care îl au de tăiat, iar apoi pornesc pe jos spre celălalt copac. Ei doresc să se organizeze în aşa fel încât suma distanţelor pe care le vor parcurge pe jos sa fie minimă.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $padurari.in$ conţine pe prima linie numerele $N$ şi $K$. Pe următoarele $N$ linii se află câte un număr întreg. A $i$-a linie conţine distanţa {$D{~i~}$} de la al $i$-ulea copac până la începutul şoselei. Distanţele sunt date în *ordine crescătoare*.

Fişierul de intrare $padurari.in$ ...

h2. Date de ieşire

În fişierul de ieşire $padurari.out$ se va afla un singur număr întreg reprezentând suma minimă a distanţelor pe care le vor parcurge pădurarii.

În fişierul de ieşire $padurari.out$ ...

h2. Restricţii

* $2 ≤ N ≤ 200 000$
* $1 ≤ K ≤ N/2$
* {$0 ≤ D{~i~} ≤ 10^9^$}
* Pentru $20%$ din teste, $N ≤ 1 000$.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. padurari.in |_. padurari.out |

| 6 2
1
6
8
12
13
16
| 3

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Un pădurar va tăia copacii $2$ şi $3$ şi un alt pădurar va tăia copacii $4$ şi $5$.

...

== include(page="template/taskfooter" task_id="padurari") ==

4071