7223번 - Vieneto transformacija 다국어

문제

Numeracijos karalystė labai didžiuojasi savo skaičių kokybe, tad renka mokesčius iš savo gyventojų už kiekvieną skaičiaus pakeitimą. Nepaisant to, Numeracijos gyventojai labai mėgsta transformuoti skaičius.

Draugų grupė Vienetukai mėgsta transformuoti skaičius, pradėdami nuo skaičiaus 1ドル$. Kadangi vienetukai nėra labai turtingi, savoms reikmėms naudoja pačias pigiausias transformacijas, kurios atliekamos tik naudojant paskutinį (mažiausiai reikšminį) skaitmenį:

• prie skaičiaus paskutinio skaitmens pridėti vienetą – kainuoja 1ドル$ auksinį;
• skaičiaus paskutinį skaitmenį padauginti iš bet kurio skaičiaus nuo 2ドル$ iki 9ドル$ – kainuoja 2ドル$ auksinius.

Pavyzdžiui, naudojant šias operacijas, skaičių 2121ドル$ iš 1ドル$ galima gauti tokia transformacijų seka:

1. 1ドル$ padauginame iš 7ドル$ – gauname 7ドル$.
2. 7ドル$ padauginame iš 3ドル$ – gauname 21ドル$.
3. Prie paskutinio skaitmens pridedame 1ドル$ – gauname 22ドル$.
4. Paskutinį skaitmenį padauginame iš 5ドル$ – gauname 210ドル$.
5. Prie paskutinio skaitmens pridedame 1ドル$ – gauname 211ドル$.
6. Paskutinį skaitmenį padauginame iš 3ドル$ – gauname 213ドル$.
7. Paskutinį skaitmenį padauginame iš 7ドル$ – gauname 2121ドル$.

Tokia transformacija kainuoja 12ドル$ auksinių. Šią seką galime pavaizduoti schematiškai:

$$ 1 \underset{1 \times 7}{\overset{2}{\Longrightarrow}} 7 \underset{7 \times 3}{\overset{2}{\Longrightarrow}} 21 \underset{1 +1}{\overset{1}{\Longrightarrow}} 22 \underset{2 \times 5}{\overset{2}{\Longrightarrow}} 210 \underset{0 + 1}{\overset{1}{\Longrightarrow}} 211 \underset{1 \times 3}{\overset{2}{\Longrightarrow}} 213 \underset{3 \times 7}{\overset{2}{\Longrightarrow}} 2121 $$

Skaičių 2121ドル$ galima buvo gauti ir pigiau, sumokant tik 9ドル$ auksinius:

$$ 1 \underset{1 \times 5}{\overset{2}{\Longrightarrow}} 5 \underset{5 \times 5}{\overset{2}{\Longrightarrow}} 25 \underset{5 \times 3}{\overset{2}{\Longrightarrow}} 215 \underset{5 \times 4}{\overset{2}{\Longrightarrow}} 2120 \underset{0 +1 }{\overset{1}{\Longrightarrow}} 2121 $$

Padėkite Vienetukams sutaupyti – raskite mažiausią kainą, už kurią Vienetukai gali gauti duotąjį skaičių $A$ iš 1ドル$ nurodytomis transformacijomis.

입력

Pirmoje įvesties eilutėje duotas natūralusis skaičius $A$.

출력

. Išveskite vieną skaičių – mažiausią kainą, už kurią Vienetukai gali gauti duotąjį skaičių $A$ iš 1ドル$. Jei skaičiaus $A$ nurodytomis transformacijomis gauti neįmanoma, išveskite $-1$.

제한

• 1ドル ≤ A ≤ 10^9$

힌트