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