Problem G
Kaffiskömmtun

Ein mikilvægasta auðlind háskóla er kaffi. Mjög mikilvægt er að þessi auðlind sé nýtt til fulls.

Til þess þarf að hella upp á kaffi reglulega. Það þarf að tímasetja þessa uppáhellingu rétt því tölvunarfræðiprófessorar hafa engan afgangs tíma. Ef ekkert kaffi er tilbúið þegar þeir fara á kaffistofuna munu þeir einfaldlega þurfa að fara aftur að kenna án þess að fá kaffi. Þeir eru hins vegar allir mjög samviskusamir og geta hellt upp á nýja könnu af kaffi þegar þeir mæta á kaffistofuna, jafnvel eftir að hafa fyllt sinn eiginn bolla. Eftir að byrjað er að hella upp á nýja könnu af kaffi þurfa að líða $T$ sekúndur áður en nýja kannan af kaffi er tilbúin. Ný kanna af kaffi getur fyllt $C$ kaffibolla.

Hver er hámarksfjöldi manns sem geta fengið sér kaffi ef við skipuleggjum uppáhellingar fullkomlega? Athugið að stundum er best að hella afgangskaffi úr könnunni og hella upp á nýtt kaffi þó það sé syndsamleg sóun á mikilvægri auðlind. Kannan er tóm í upphafi.

Inntak

Fyrsta lína inntaksins innheldur þrjár heiltölur $N$, fjölda prófessora sem fara í kaffipásu, þar sem $1 \leq N \leq 10^6$, $C$, fjölda bolla sem ein kanna getur fyllt, þar sem $1 \leq C \leq 500$, og $T$, fjölda sekúndna sem það tekur fyrir nýja könnu að vera tilbúna, þar sem $1 \leq T \leq 10^9$. Næst kemur ein lína með $N$ heiltölum $1 \leq t_1 \leq t_2 \leq \dots \leq t_ N \leq 10^9$, tímasetningarnar þegar prófessorarnir fara í kaffipásu.

Úttak

Prenta skal hámarksfjölda prófessora sem geta fengið kaffi þegar þeir fara í pásu.

5 2 10
1 8 12 23 25

3

7 3 4
1 4 5 6 8 10 12

4