Sürətli Yazı#1930
Vasya yazmaqda az təcrübəyə malikdir, buna görə də tez-tez lazım olan düymələri tapmaq üçün klaviaturaya baxmalı olur və yenə də səhvlərə yol verir. Sadəlik üçün fərz edək ki, o, yalnız bir növ səhv edir: bir simvolu digəri ilə əvəz edir. Səhvləri düzəltmək üçün o, aşağıdakı strategiyadan istifadə edir: vaxt aşırı ekrana baxır və əgər mətnin içində hər hansı bir səhv varsa, mətnin sonundan ilk etdiyi səhvə qədər olan bütün simvolları silir (yəni yalnız düzgün olan hissəni saxlayır) və həmin mövqedən yenidən yazmağa davam edir, bunun üçün 'backspace' düyməsini bir neçə dəfə basır.
Hər hansı bir düymənin (o cümlədən 'backspace') basılması 1 vahid vaxt aparır, ekrana baxmaq isə vahid vaxt tələb edir. Hər simvol üçün səhv etmə ehtimalı verildikdə, bütün mətnin düzgün şəkildə yazılması üçün (sonda ekrana baxıb səhv olmadığını təsdiqləmə daxil olmaqla) minimal mümkün gözlənilən vaxtı hesablayın.
Mətn simvoldan ibarətdir və -ci simvolun səhv yazılması ehtimalı a_i-dir.
Giriş faylında iki tam ədəd və (1 \leq n \leq 3000, 1 \leq t \leq 10^6), ardınca ədəd həqiqi ədəd a_i (10^{-5} \leq a_i \leq \frac{1}{2}) verilir.
Bir real ədəd çıxış verin — minimal mümkün gözlənilən vaxtı. Sizin cavabınız düzgün cavabla 10^{-6} nisbi xəta daxilində qəbul edilir.
Nümunə 1