5. Okno do študentovej duše

Miško by si mal robiť domácu. A ísť postrúhať mrkvu. A už niekedy konečne pozrieť zo záznamu minulotýždňovú prednášku z toho či onoho predmetu. A pozbierať si zo sušiaka prádlo, nech sa dá prať ďalšia várka. A upratať po mačke, ktorá podľa zvuku práve zase na chodbe nagrcala. List povinností pokračuje ďalej a ďalej.

Čím je povinností viac, tým sa do nich Miškovi menej chce. A tak si radšej skúma najnovšiu matematickú zaujímavosť, na ktorú práve narazil: správanie sa ciferných súčinov keď ich robíme opakovane.

Začnime napríklad z čísla 47. Jeho ciferný súčin je \(4\times 7 = 28\). Ciferný súčin čísla 28 je \(2\times 8 = 16\). Ciferný súčin čísla 16 je \(1\times 6 = 6\). No a odkedy sme sa dostali k jednocifernému číslu, už je to nuda: ciferným súčinom jednociferného čísla je ono samo. Ak teda časom dosiahneme jednociferné číslo, celý postup ukončíme.

Niekedy je tento proces rýchlejší, inokedy pomalší. Napríklad číslo \(987\,654\,321\) má ciferný súčin \(9! = 326\,880\) a číslo \(326\,880\) má ciferný súčin 0. Hoci sme začali s oveľa väčším číslom ako v predošlom príklade, skončili sme skôr. A možno sa niekedy stane aj to, že pre nejaký začiatok vôbec nikdy neskončíme na jednocifernom čísle. Alebo žeby sa to predsa len nemohlo stať? O tom Miško zatiaľ nič netuší.

Miško sa rozhodol, že niektorým nezáporným celým číslam priradí skóre, a to nasledovne:

• Každé jednociferné číslo \(n\) dostane priradené Miškom zvolené malé nezáporné skóre \(z_n\).
• Ak má viacciferné číslo \(n\) ciferný súčin \(s(n)\) a číslo \(s(n)\) má skóre \(x\), číslo \(n\) dostane skóre \(x+1\).

Úloha

Na vstupe dostanete hodnoty \(z_0\) až \(z_9\) a tiež cieľové skóre \(c\). Vašou úlohou je nájsť najmenšie nezáporné celé číslo, ktoré má skóre \(c\).

Poriadne si pozrite obmedzenia pre veľkosť vstupu.

Formát vstupu

V prvom riadku vstupu sú čísla \(z_0\) až \(z_9\), v druhom je číslo \(c\).

Formát výstupu

Vypíšte jeden riadok a v ňom jedno číslo – najmenšie nezáporné celé číslo so zadaným skóre.

Obmedzenia a hodnotenie programov

Obmedzenia použité v testoch sme zvolili tak, že v každom teste správna odpoveď existuje (toto nie je úplne zjavné) a navyše vždy platí, že má hodnotu nanajvýš \(10^{18}\) (toto už vonkoncom nie je zjavné ale tiež je to pravda). Tieto predpoklady môžete využiť vo svojich riešeniach.

Sú štyri sady vstupov. Vo všetkých štyroch platí:

• hodnoty \(z_i\) sú z rozsahu od 0 po 3
• ak označíme \(m=\max z_i\), tak každú z hodnôt od 0 po \(m\) má aspoň jedno \(z_i\)
• \(c\) je z rozsahu od 0 po 11

Navyše v prvej sade platí, že odpoveď je nanajvýš 1000, v druhej sade platí, že odpoveď je z rozsahu od 1000 po \(1\,000\,000\) a v tretej sade platí, že všetky \(z_i\) sú rovné nule.

Hodnotenie popisov

Pri hodnotení popisu nezáleží na asymptotickej zložitosti vášho riešenia (keďže všetky čísla na vstupe sú veľmi malé). Ľubovoľné riešenie dosť efektívne na to, aby získalo body za vstupy, môže dostať do 10 bodov za dôkaz toho, že dáva vždy korektný výstup. Posledné dva body sa budú udeľovať za efektívnosť hľadania.

Príklady

Input:

0 1 1 1 1 1 1 1 1 1
2

Output:

11

• Číslo 0 má skóre 0.
• Čísla od 1 po 9 majú skóre 1.
• Číslo 10 má ciferný súčin 0, a keďže 0 má skóre 0, tak 10 má skóre 1.
• Číslo 11 má ciferný súčin 1, a keďže 1 má skóre 1, tak 11 má skóre 2.

Input:

0 0 0 0 0 0 0 0 0 0
3

Output:

39

• Číslo 4 má skóre 0, číslo 14 má ciferný súčin 4 a teda skóre 1, číslo 27 má ciferný súčin 14 a teda skóre 2, no a číslo 39 má ciferný súčin 27 a teda skóre 3.
• Žiadne menšie číslo ako 39 nemá skóre 3.

Input:

2 0 0 0 0 0 0 0 0 1
2

Output:

0

Input:

2 1 2 2 1 1 1 0 1 0
6

Output:

268