مسئولین آشپزخانه شریف به تازگی روش فروش غذای خود را عوض کرده‌اند و در ازای کوپن‌های خاص به دانشجویان غذا می‌دهند. کاغذی بلندبالا که روی آن رشته‌ی $s$ از حروف کوچک انگلیسی و '*' نوشته شده است، به دست علیرضا رسیده است.

علیرضا با مهارت مثال‌نزدنی خودش، می‌تواند هر ستاره را با حرفی دلخواه از حروف کوچک انگلیسی جایگزین کند. بعد از آن، با تعداد دلخواهی برش، کاغذ را به تعدادی تکه کاغذ مجزا تقسیم می‌کند که روی هر تکه کاغذ یک رشته وجود دارد. علیرضا به ازای هر تکه کاغذی که رشته نوشته شده روی آن برابر با یکی از کوپن‌ها باشد، دقت کنید که ممکن است کوپن روی چند تکه کاغذ نوشته شود؛ در این صورت به تعداد تکه کاغذها غذا دریافت می‌کند.

بیش‌ترین تعداد غذایی که او می‌تواند از آشپزخانه بگیرد، چندتاست؟

در خط اول رشته $s$ می‌آید. این رشته تنها شامل حروف کوچک انگلیسی و حرف '*' است.

در خط دوم عدد طبیعی $n$ تعداد کوپن‌های مختلف آشپزخانه می‌آید.

در $i$ امین خط از $n$ خط بعدی رشته $t_i$ می‌آید که نمایانگر رشته مربوط کوپن‌ها هستند.

در تنها خط خروجی بیشینه تعداد غذایی که علیرضا می‌تواند از آشپزخانه دانشگاه بگیرد را چاپ کنید.

• زیرمسئله اول (۵ نمره): $|s| \leq 10\,000, \displaystyle\sum\limits_{i=1}^{n} |t_i| \leq 10\,000$
• زیرمسئله دوم (۳۱ نمره): در رشته $s$ حرف '*' نمی‌آید.
• زیرمسئله سوم (۱۷ نمره): در رشته $s$ حرف '*' حداکثر یک بار می‌آید.
• زیرمسئله چهارم (۴۷ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۵ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت
• $|s| \leq 1\,000\,000$
• $\displaystyle\sum\limits_{i=1}^{n} |t_i| \leq 1\,000\,000$
• رشته $s$ حداکثر ۵۰ حرف '*' دارد.

• سوال قبل
• سوال بعد