Друзья Манао часто присылают ему новые песни. Обычно он слушает их не сразу, а собирает их в плейлист. Когда он чувствует, что его ум открыт для новой музыки, он включает этот плейлист и начинает прослушивать песни.
Конечно, Манао нравится далеко не каждая песня. Чтобы получить побольше удовольствия от присланных песен, он придумал следующую процедуру прослушивания плейлиста:
- Если, прослушав некоторую песню, Манао понял, что она ему понравилась, он запоминает ее и начинает слушать следующую непрослушанную песню.
- Если, прослушав некоторую песню, Манао понял, что она ему не понравилась, он слушает все понравившиеся ему до этого момента песни и только потом начинает слушать следующую непрослушанную песню.
Например, если у Манао в плейлисте четыре песни A, B, C, D (в соответствующем порядке) и ему в итоге понравятся песни A и C, тогда порядок прослушивания получится следующий:
- Манао слушает A, ему она нравится, запоминает.
- Манао слушает B, ему она не нравится, поэтому он снова слушает A.
- Манао слушает C, песня ему нравится и он ее тоже запоминает.
- Манао слушает D, не получает от нее удовольствия и заново слушает песни A и C.
То есть в итоге Манао прослушает три раза песню A, два раза песню C и по одному разу песни B и D. Заметим, что если песня однажды понравилась Манао, она не может разонравиться ему при следующем прослушивании.
Манао прислали n песен: i-ая из них длится li секунд и может понравиться Манао с вероятностью pi процентов. Песни могли попасть в плейлист Манао в любом порядке, поэтому Манао хочет знать максимальное математическое ожидание количества секунд, после которого процесс прослушивания закончится, по всем возможным перестановкам песен в плейлисте.
Выходные данные
В единственной строке выведите одно вещественное число — максимальное по всем перестановкам песен математическое ожидание длительности процесса прослушивания. Ответ будет считаться верным, если абсолютная или относительная погрешность не будет превышать 10 - 9.
Примечание
Рассмотрим первый тестовый пример. Если слушать песни в том порядке, в котором они заданы изначально, математическое ожидание будет равно 467.5 секунд. Максимальное математическое ожидание получается, если переставить первую песню в конец плейлиста.
Рассмотрим второй тестовый пример. Песню длиной 360 секунд нужно слушать первой, а песню длиной 300 секунд, которая определенно не понравится Манао — последней.