+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- یک دستگاه خودپرداز داریم که روی آن ۱۰ دکمه برای وارد کردن **هر رقم** و یک دکمه برای **پاک کردن** سمت راست‌ترین رقم عدد وارد شده، وجود دارد. می‌خواهیم با این دستگاه، عدد $n$ را وارد کنیم. اما می‌دانیم ۱۰ دکمه ارقام این دستگاه خراب است ولی دکمه پاک کردن، به درستی کار می‌کند.  ما مشکل دستگاه را فهمیده‌ایم و می‌دانیم اگر دکمه رقم $d$ وارد شود، رشته $s_d$ (به همان ترتیب) وارد دستگاه می‌شود. همچنین مطمئن هستیم که رقم اول رشته $s_d$ خود $d$ است. ممکن است $s_d$ شامل رقم تکراری باشد. حال از شما می‌خواهیم کمترین تعداد فشار دادن دکمه‌ها که برای وارد کردن عدد $n$ لازم است را محاسبه کنید. # ورودی در سطر اول ورودی عدد صحیح و مثبت $n$ داده می‌شود. $$1 \leq n \leq 10^{1000}$$ در ۱۰ سطر بعدی در سطر $d$ام رشته $s_d$ آمده است. $$ 1 \leq |s_d| \leq 10$$ تضمین می‌شود که رقم اول $s_d$ خود $d$ است ولی ممکن است $s_d$ رقم تکراری داشته باشد. # خروجی در تنها سطر خروجی، کمینه تعداد عملیات لازم برای وارد کردن عدد $n$ را بنویسید. # مثال‌ها ---------- ## ورودی نمونه ۱ ``` 140102 0 1 2 3 4 5 6 7 8 9 ``` ## خروجی نمونه ۱ ``` 6 ``` <details class="white"> <summary>**توضیح نمونه ۱**</summary> دستگاه خودپرداز بالا سالم است. یعنی با فشار دادن دکمه هر رقم، فقط همان رقم نوشته می‌شود؛ پس کافی است برای نوشتن عدد $140102$ به صورت زیر عمل کنیم. + **عملیات اول.** قبل از انجام این عملیات، هیچ رقمی وارد دستگاه نشده است، پس با فشار دادن دکمه ‍‍`1`، عدد $1$ وارد دستگاه می‌شود. + **عملیات دوم.** تا قبل از این عملیات عدد $1$، وارد شده است. در این عملیات با فشار دادن دکمه `4`، عدد $14$ وارد دستگاه می‌شود. + **عملیات سوم.** تا قبل از این عملیات عدد $14$، وارد شده است. در این عملیات با فشار دادن دکمه `0`، عدد $140$ وارد دستگاه می‌شود. + **عملیات چهارم.** تا قبل از این عملیات عدد $140$، وارد شده است. در این عملیات با فشار دادن دکمه `1`، عدد $1401$ وارد دستگاه می‌شود. + **عملیات پنجم.** تا قبل از این عملیات عدد $1401$، وارد شده است. در این عملیات با فشار دادن دکمه `0`، عدد $14010$ وارد دستگاه می‌شود. + **عملیات ششم.** تا قبل از این عملیات عدد $14010$، وارد شده است. در این عملیات با فشار دادن دکمه `2`، عدد $140102$ وارد دستگاه می‌شود. </details> ---------- ## ورودی نمونه ۲ ``` 18415 0 15 2 3 415 59 6 7 84 9 ``` ## خروجی نمونه ۲ ``` 4 ``` <details class="white"> <summary>**توضیح نمونه ۲**</summary> دستگاه فوق خراب است. برای وارد کردن عدد $18415$ با کمترین تعداد عملیات می‌توانیم به صورت زیر عمل کنیم. + **عملیات اول.** قبل از انجام این عملیات، هیچ رقمی وارد دستگاه نشده است، پس با فشار دادن دکمه ‍‍`1`، عدد $15$ وارد دستگاه می‌شود. + **عملیات دوم.** تا قبل از این عملیات عدد $15$، وارد شده است. در این عملیات با پاک کردن آخرین رقم، عدد وارد شده به $1$ تغییر می‌کند. + **عملیات سوم.** تا قبل از این عملیات عدد $1$، وارد شده است. در این عملیات با فشار دادن دکمه `8`، عدد $184$ وارد دستگاه می‌شود. + **عملیات چهارم.** تا قبل از این عملیات عدد $184$، وارد شده است. در این عملیات با فشار دادن دکمه `1`، عدد $18415$ وارد دستگاه می‌شود. </details> ---------- ## ورودی نمونه ۳ ``` 18415 0 16 2 3 415 59 6 7 84 9 ``` ## خروجی نمونه ۳ ``` 5 ``` <details class="white"> <summary>**توضیح نمونه ۳**</summary> دستگاه فوق خراب است. برای وارد کردن عدد $18415$ با کمترین تعداد عملیات می‌توانیم به صورت زیر عمل کنیم. + **عملیات اول.** قبل از انجام این عملیات، هیچ رقمی وارد دستگاه نشده است، پس با فشار دادن دکمه ‍‍`1`، عدد $16$ وارد دستگاه می‌شود. + **عملیات دوم.** تا قبل از این عملیات عدد $16$، وارد شده است. در این عملیات با پاک کردن آخرین رقم، عدد وارد شده به $1$ تغییر می‌کند. + **عملیات سوم.** تا قبل از این عملیات عدد $1$، وارد شده است. در این عملیات با فشار دادن دکمه `8`، عدد $184$ وارد دستگاه می‌شود. + **عملیات چهارم.** تا قبل از این عملیات عدد $184$، وارد شده است. در این عملیات با پاک کردن آخرین رقم، عدد وارد شده به $18$ تغییر می‌کند. + **عملیات پنجم.** تا قبل از این عملیات عدد $184$، وارد شده است. در این عملیات با فشار دادن دکمه `4`، عدد $18415$ وارد دستگاه می‌شود. </details>