== 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 ce 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. "Pistolul" omoara INSTANT primu zombie din fata lui cu costul de 1 chakra
2. "Bulanizatorul" 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]

h2. Exemplu