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

Domnitorul "Stefan cel Tare" este invadat de zombie. El l-a chemat pe "Adi copilul Magic" sa il salveze. "Adi copilul Magic" se afla intr-un tunel de lungime D metri la punctul 0 iar deoarece are pile la "Mircea Inteligenta" a aflat ca sunt N zombie si pentru fiecare zombie stie la ce moment de timp apare in tunel. Toti zombii intra in tunel in punctul D si merg catre "Adi copilul Magic" cu un metru pe secunda. "Adi copilul Magic" trebuie sa distruga toti zombii. El a primit de la "Stefan cel Tare" o arma care la un moment distruge instant primu zombie din fata lui cu costul 1. Plictisit "Adi copilul Magic" s-a dus la "Vali baiatul cu Arma" si a facut rost de o noua arma. Arma se numeste "Cocalizratorul". La un moment de timp "Cocalizratorul" distruge instant toti zombii din tunel cu costul K.

 
Pe o strada formata din $D$ patratele apar din capatul dreapta zombii la momente diferite de timp. Sunt $N$ zombii iar pentru fiecare stii momentul de timp cand intra in casuta $D$. Toti zombii dupa ce intra pe strada merg cu viteza de $1$ casuta pe secunda catre capatul stanga. Vrajitorul cel bun se afla fix in stanga capatului din stanga (patratelul $0$ ) si trebuie sa omoare toti zombii fara ca acestia sa ajunga la el. El are $2$ vraji:
 
1. $"Rasengan"$ omoara $INSTANT$ primu zombie din fata lui cu costul de $1$ chakra
2. $"Rasen Shuriken"$ omoara $INSTANT$ toti zombii de pe strada cu costul de $K$ chakra

h2. Date de intrare

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

Fişierul de intrare $zombie.in$ va contine pe prima linie $3$ numere naturale $D, N, K$ cu semnificatia din enunt iar pe a doua linie se vor afla $N$ numere naturale reprezentand momentele de timp la care intra cei $N$ zombii pe strada.

h2. Date de ieşire

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

În fişierul de ieşire $zombie.out$ va contine un singur numar natural reprezentand chakra minima care trebuie sa o foloseasca vrajitorul pentru a omora toti zombii.

h2. Restricţii

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

* $1 ≤ D ≤ 1.000.000.000$
* $1 ≤ N ≤ 1.000.000$
* $1 ≤ K ≤ 1.000.000$
* momentele de timp la care apar zombii sunt diferite doua cate doua si sunt cuprinse in intervalul $[1,1.000.000.000]$
* momentele de timp la care apar zombii se dau in ordine crescatoare

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

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

| 5 5 2
1 10 11 12 13| 3|

h3. Explicaţie

...

Primul zombie poate sa il omoare cu $"Rasengan"$ consumand $1$ chakra iar pe ceilalti patru poate sa ii omoare pe toti cu $"Rasen Shuriken"$ consumand $2$ chakra.

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

6374