+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- شنگدباو در فراق یار و نبود کار حوصله‌اش سر رفته‌ بود و تصمیم به حل سوالی گرفت. صورت سوال طولانی بود. به قول یکی از دوستان شنگدباو «همیشه که نباید سوالا رو پیچوند! بعضی وقتا باید ساده حرف زد!» در نتیجه تصمیم گرفت حالت ساده شده‌ی صورت سوال را قرار دهد: تعداد $n$ رشته داده شده است، رشته‌ی $i$ام $s_i$ می‌باشد. به ازای هر رشته لیستی از اعداد موجود است، لیست متناظر با رشته‌ی $i$ام شامل $|s_i| + 1$ عدد است که عدد $j$ام آن (با شروع از صفر)‌ مقدار $a_{i,j}$ دارد. ($1 \le i \le n$ ،$0 \le j \le|s_i|$) هزینه‌ی رفتن از رشته‌ی $s_i$ به $s_j$ برابر است با $a_{j , lcp(s_i , s_j)}$ (منظور از $lcp(s , p)$ طول بزرگترین پیشوند مشترک دو رشته‌ی $s$ و $p$ است) فرض کنید روی رشته‌ی $s_A$ قرار داریم و می‌خواهیم به رشته‌ی $s_B$ برسیم. کمینه هزینه برای انجام این‌ کار را باید خروجی دهید.» شنگدباو سوال را حل کرده است! آیا شما هم می‌توانید آن‌ را حل کنید؟ # ورودی در سطر اول ورودی عدد $n$ داده شده است. سپس در $2\times n$ سطر بعدی ابتدا رشته‌ی ناتهی $i$ ام آمده است و سپس لیست متناظر با رشته‌ی مورد نظر آمده‌ است. در سطر آخر نیز ۲ عدد آمده است که اولی $A$ و دومی $B$ است. $$1 \le n \le 500\ 000$$ $$0 \le a_{i,j} \le 10 ^ 9$$ $$\sum |s_i| \le 500\ 000$$ $$A \ne B$$ + رشته های ورودی از حروف کوچک الفبا تشکیل شده‌اند. # خروجی در تنها سطر خروجی کمترین هزینه برای رفتن از $s_A$ به $s_B$ را خروجی دهید. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۲۰ | $n \le 5\ 000$| | ۲ | ۲۰ | به ازای هر $0 \le j < abs(s_i)$ داریم: $a_{i , j+1} - a_{i , j} = 1$| | ۳ | ۲۰ | رشته‌ها فقط از حروف $a$ و $b$ تشکیل شده اند.| | ۴ | ۴۰ | بدون محدودیت اضافی| # مثال ## ورودی نمونه ۱ ``` 3 a 0 1 b 0 1 a 0 1 1 3 ``` ## خروجی نمونه ۱ ``` 0 ``` ## ورودی نمونه ۲ ``` 3 abcd 0 1 2 3 4 abc 0 1 2 3 abcde 0 1 2 10 1 2 2 3 ``` ## خروجی نمونه ۲ ``` 4 ``` ## ورودی نمونه ۳ ``` 4 shengdebao 10 11 12 13 14 15 16 17 18 19 20 bao 4 3 2 7 barricade 1 13 12 11 10 9 8 7 6 5 baran 7 14 3 14 7 6 1 4 ``` ## خروجی نمونه ۳ ``` 6 ```