scandura

Scandura

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

Poveste şi cerinţă...

G. Tamplaru' I vrea sa-si faca un birou nou. El cunoaste dimensiunile finale ale tuturor scandurilor de care are nevoie pentru a construi biroul si a cumparat o scandura de lungime $L$ egala cu suma lungimilor tuturor scandurilor necesare. El are o masina speciala in care poate introduce o scandura de orice lungime si aceasta o taie in maxim $M$ bucati. Efortul depus de G. Tamplaru' I pentru a taia o scandura de lungime $X$ este egal cu $X$. El nu vrea sa munceasca prea mult si va cere voua sa determinati efortul minim necesar taierii scandurii mari in lungimile dorite.

h2. Date de intrare

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

Fişierul de intrare $scandura.in$ va contine pe prima linie doua numere naturle $N$ si $M$. Pe a doua linie se vor afla, separate prin spatii, $N$ numere naturale *in ordine crescatoare*.

h2. Date de ieşire

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

În fişierul de ieşire $scandura.out$ se va afisa pe prima linie efortul minim necesar.

h2. Restricţii

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

* $1 ≤ N ≤ 10^6^$
* $2 ≤ M ≤ N$
* $1 ≤ lungimile scandurilor ≤ 2 * 10^9^$
* Rezultatul se va incadra intotdeauna in tipuri de date intregi pe $64$ de biti cu semn

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

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

| 4 2
1 2 3 4
| 19

|
h3. Explicaţie

...

Scandura initiala are lungime $10$. G. Tamplaru' I efectueaza o taiere cu costul $10$ si obtine 2 scanduri de lungime $4$ si $6$. Scandura de lungime $6$ o taie apoi in 2 scanduri de lungme $3$. In final, una din cele 2 scanduri de lungime $3$ este taiata intr-o scandura de lungime $1$ si una de lungime $2$.
 
Efortul total este egal cu $10 + 6 + 3 = 19$.

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

3473