• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

میهمان‌ها که از جشن با شکوه ابواسحاق بسیار لذت برده بودند تصمیم گرفتند هر یک نامه‌ای برای تشکر، به او بفرستند. او نیز برای ثبت این خاطره‌ی زیبا بنا به ساختن رشته‌ای زیبا کرد.

ابواسحاق $n$ نامه، $s_1, s_2, ..., s_n\ $ از حروف کوچک انگلیسی دریافت کرده و نامه $i$ام را $c_i$ واحد دوست دارد.

زیبایی رشته $T$ برای او به صورت زیر تعریف می‌شود (تابع $occurs(s, t)$ تعداد تکرارهای رشته $t$ در رشته $s$ را مشخص می‌کند): $$b(T) = \dfrac{\sum^{n}_{i=1} c_i * occurs(T, s_i)}{|T|}$$

ابواسحاق که می‌خواهد زیباترین رشته را بسازد، لازم است بیشترین مقدار $b(T)$ را به ازای همه رشته‌های به طول $10^{100}$ محاسبه کند.

او که پس از جشن بسیار خسته شده از شما می‌خواهد تا این مقدار را برایش محاسبه کنید.

ورودی

در خط اول ورودی $n$ که نمایانگر تعداد رشته‌ها است آمده است. در خط بعدی $n$ عدد $c_i$ آمده‌اند. سپس در $n$ خط بعدی، در هر خط $s_i$ می‌آید.

$$1 \le \sum^{n}_{i=1} |s_i| \le 500$$ $$1 \le c_i \le 10^9$$

خروجی

در تنها خط خروجی مقدار خواسته شده را چاپ کنید. در صورتی که جواب شما $y$ باشد و جواب واقعی $x$ باشد؛ جواب شما مورد قبول است اگر شرط $\dfrac{|x-y|}{x} \le 10^{-6}$ برقرار باشد.

مثال

ورودی نمونه ۱

1
10
aa

خروجی نمونه ۱

10.000000

در این نمونه به ازای رشته $T$ که از $10^{100}$ تا کاراکتر a تشکیل شده، مقدار $F$ برابر با $10 - 10^{-100}$ است که با دقت شش رقم اعشار ۱۰ می‌شود.

ورودی نمونه ۲

4
2 3 4 5
abb
bba
aab
baa

خروجی نمونه ۲

3.500000