3. Opravte matfyz

Po výskyte ploštíc na matfyze vedeniu došla trpezlivosť. Rozhodlo sa urobiť jeho kompletnú prerábku.

Gratulujeme! Tvoja stavebná firma Kopu Stavieb Postavím vyhrala verejné obstarávanie a teraz má zabezpečiť prerábanie matfyzu. Prerábka pozostáva z úloh, pričom o každej vieš ako dlho trvá jej dokončenie. K dispozícii máš stavbyvedúceho, zároveň si môžeš najať niekoľko robotníkov. Predtým, ako sa robotník zapojí do práce, musí absolvovať školenie u stavbyvedúceho, ktorý počas toho nepracuje. Bez stavbyvedúceho na stavbe sa robotníci flákajú a nepracujú. Ako rýchlo dokážeš vykonať prerábku?

Úloha

Úlohou je nájsť najrýchlejší možný čas za aký sa dá stihnúť vykonať \(n\) úloh, pričom každá trvá \(t\) hodín. Na začiatku máš iba stavbyvedúceho, ale na začiatku každej hodiny si môžeš najať najviac \(r\) robotníkov. Robotníci musia absolvovať povinné školenie u stavbyvedúceho, ktorý počas tej doby nepracuje. Každý robotník je inak šikovný a trvá mu iný čas, kým bude zaškolený. Stavbyvedúci dokáže školiť jedného robotníka naraz. Bez stavbyvedúceho sa nepracuje. Po absolvovaní školenia dokáže robotník pracovať rovnako rýchlo ako stavbyvedúci. Na každej úlohe môže pracovať najviac 1 človek (či už robotník, alebo stavbyvedúci).

Formát vstupu

Na vstupe je jediný riadok, na ktorom sú medzerou oddelené čísla \(n,t,r\;(1\leq t\leq 5\,000)\) – počet úloh, trvanie jednej úlohy, a počet robotníkov, ktoré máš k dispozícii. Na druhom riadku je \(r\) medzerou oddelených čísel \(p_i; (1\leq p\leq 100\,000)\) – čas, koľko trvá zaškoliť \(i\)-teho robotníka. Platí, že:

• v prvej sade platí, že školenie aj vykonanie úlohy trvá vždy 1 (\(\forall i: p_i=t=1\))
• v druhej a tretej sade platí, že školenie trvá vždy rovnako ako vykonanie úlohy (\(\forall i: p_i=t\))
• o zvyšných piatich sadách nemôžete nič predpokladať

Pre premenné platia nasledujúce obmedzenia:

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo, najkratší možný počet hodín za ktorý sa dá stihnúť prerábka.

Príklady

Input:

2 2 3
3 2 1

Output:

3

Samotný stavbyvedúci by prácu vykonal za \(2\cdot 2=4\) hodiny, ale viac sa oplatí, ak hneď na začiatku za 1 hodinu zaškolí jedného (tretieho) robotníka, a potom tento robotník spolu s ním urobí každý jednu 2 hodiny trvajúcu úlohu. Celkovo teda stavba bude trvať len \(2+1=3\).

Input:

1 2 3
1 2 3

Output:

2

Pri jednej úlohe sa neoplatí najímať robotníka.

Input:

3 3 3
50 50 50

Output:

9

Školenie robotníka by trvalo tak dlho, že sa viac oplatí robiť všetko sám.