2. Absurdne drahá pizza

Miestnosť T2, niekedy začiatkom novembra:

“Už ste to počuli? Zdraželi pizzu v matickej jedálni! Čo budeme teraz robiť? Sme chodobní študenti, toľko si nemôžeme dovoliť zaplatiť za pizzu.”, rozliehalo sa v T2.

“Nebojte, mám plán”, povedal Krtko, “Aďo doniesie tú pizza piecku čo sľúbil, a budeme si piecť pizzu tu.”

“To by som nerobil, viete ako veľmi zdraželo droždie?”, ozval sa Kubo, ktorý sa z ničoho nič objavil v T2 tiež.

“Tak budeme robiť kváskové cesto. To len zoženieme zopár kváskov, a oni potom budú rásť samé…”

…

Tak sa aj stalo. Nakúpili sa kvásky do T2, s tým, že sa z nich bude piecť pizza. Bohužiaľ, prišiel lockdown, a vedúci prestali chodiť do T2. A tak tam kvásky len tak ležali, nikto z nich nebral, a nepozorovane sa delili na viac a viac kváskov.

Vedeli by ste vypočítať, koľko kváskov bude v T2, keď sa vrátime do školy?

Úloha

Do T2 sa nakúpilo presne \(n\) kváskov.

Rast kváskov funguje nasledovne: Každý kvások má svoj čas – počet dní do rozdelenia kvásku na viac kváskov. Tento čas je číslo od \(0\) po \(8\) (vrátane). Kvások sa rozdelí vtedy, keď je jeho čas rovný \(0\). Z každého kvásku vznikne presne \(k\) ďalších kváskov s časom \(8\). Čas pôvodného kvásku sa nastaví späť na \(6\).

Vašou úlohou je povedať, koľko kváskov bude v T2 po \(t\) dňoch.

Formát vstupu

Na prvom riadku sa nachádzajú \(3\) medzerou oddelené čísla \(n\) – počet kváskov v T2, \(k\) – počet kváskov na ktoré sa každý kvások rozdelí keď dosiahne čas 0 a \(t\) – deň, v ktorý nás zaujíma počet kváskov.

Na druhom riadku sa nachádza \(n\) medzerou oddelených čísel \(c_i\) – časy jednotlivých kváskov v deň \(0\).

Formát výstupu

Na výstup vypíšte jedno číslo, počet kváskov po \(t\) dňoch. Dajte si pozor, že toto číslo môže byť veľké. Odporúčame použiť \(64\) bitovú premennú (long long v C/C++).

Nezabudnite za číslom vypísať znak konca riadku.

Hodnotenie

Sú 4 sady vstupov. Platia v nich nasledovné obmedzenia:

V druhej sade navyše platí, že všetky časy kváskov sa rovnajú.

Príklad

Input:

3 2 3
2 0 6

Output:

7

Kvásky budú vyzerať nasledovne. Po prvom dni vzniknú z druhého kvásky \(2\) ďalšie, a teda (ak nové kvásky pridávame na koniec) kvásky budú mať časy 1 6 5 8 8. Po druhom dni budú mať kvásky časy 0 5 4 7 7. Po treťom vzniknú ďalšie dva kvásky (tie opäť pridávame na koniec), a teda budú mať časy: 6 4 3 6 6 8 8. Kváskov po \(3\) dňoch bude 7.

Input:

3 0 2
1 2 3

Output:

3

V tomto prípade z každého kvásku vznikne \(0\) ďalších, a teda sa počet kváskov vôbec nemení.

Input:

1 1 11
1

Output:

4

V tomto prípade v čase 10 budú časy kváskov 4 6 6 8