mafioti

Cerință

$M$ mafioți au pus stăpânire peste orașul Grozburg. Acesta este reprezentat sub forma axei Ox a sistemului de coordonate, la fiecare coordonată întreagă pozitivă aflându-se câte o cladire. Se știe că dintre toate clădirile orașului, $N$ sunt bănci unde mafioții își pot depunde câștigurile ilegale. Fiecare mafiot își poate folosi influența pentru a obține controlul a unui interval de fix $K$ clădiri consecutive ale orașului. Pentru a nu stârni suspiciunile DIICOT, mafioții doresc ca un număr minim de clădiri din oraș să se afle sub influența acestora. O clădire este considerată ca fiind sub influența mafioților dacă este sub influența a cel puțin unuia dintre ei.

Mafioții trebuie să își aleagă intervalele de clădiri (nu neapărat disjuncte) astfel încât fiecare să își poată alege o bancă din intervalul său pe care o va folosi pentru a își depunde câștigurile sale. Doi mafioți nu își pot alege aceeași bancă pentru depunerea câștigurilor, chiar dacă banca se află în intervalele amândurora. Pentru ca cei $M$ mafioți să conviețuiască în liniște, fiecare trebuie să aibă banca sa proprie.

Voi trebuie să alegeți intervalele de influență ale fiecărui mafiot astfel încât să se respecte restricțiile de mai sus și un număr minim de clădiri să fie sub influența acestora.

Date de intrare

Pe prima linie a fişierului mafioti.in se află $N$, $M$ şi $K$, numărul de bănci din oraș, numărul de mafioți, respectiv lungimea intervalului de influență. Următoarea linie conţine $N$ numere întregi pozitive și distincte, al $i$-lea din aceste numere reprezentând coordonata celei de-a $i$-a bănci.

Date de ieșire

Pe prima (şi singura) linie a fişierului mafioti.out trebuie să afişaţi numărul minim de clădiri de sub influența mafioților astfel încât să fie respectate regulile de mai sus.

Restricții și precizări

• $1 \leq N \leq 5 \ 000$
• $1 \leq M \leq 1 \ 000$
• $1 \leq K \leq 1 \ 000 \ 000 \ 000$
• Coordonatele cladirilor se afla in intervalul $[1, 1 \ 000 \ 000 \ 000]$
• Pentru $40\%$ din teste $N \leq 500$

Exemplu

mafioti.in

6 4 4
1 3 4 5 7 8

mafioti.out

5

Explicație

Primul mafiot alege clădirile $1, 2, 3, 4$ (controlează banca $1$). Al doilea alege clădirile $1, 2, 3, 4$ (controlează banca $3$). Al treilea alege clădirile $2, 3, 4, 5$ (controlează banca $4$). Al patrulea alege clădirile $2, 3, 4, 5$ (controlează banca $5$). În total mafioții controlează un minimum de $5$ clădiri.