Задача Pies Дуже егоїстичний суб'єкт (ДЕС) побачив N пиріжків, викладених у ряд. Як виявилося, кожен пиріжок має свою смачність, тобто смачності всіх пиріжків задані числами a1, a2, ..., aN. За кожну хвилину можна взяти і з'їсти один крайній (або перший, або останній) пиріжок; після цього першим чи останнім стає той, який досі був другим чи передостаннім відповідно. За кожну хвилину смачність кожного пиріжка, який ще не почали їсти, зменшується на K% (K ціле, з проміжку 1<=K<=50, одне й те саме для всіх пиріжків). Кожні K% рахуються не від початкової смачності, а від поточної; наприклад, при K=20 та початковій смачності 1000 через хвилину вона буде 800, ще через хвилину 640, потім 512, потім 409.6, і так далі. Тому ДЕС хотілося б з'їсти їх якомога швидше... але, на жаль, з'їсти за одну хвилину більше, ніж один пиріжок, просто фізично не виходить. ДЕС має чималий досвід у тому, щоб робити дії, насправді вигідні в першу чергу йому самому, й видавати їх за благодійництво. Тому він швидко здогадався, що можна практично миттєво, віддавати крайні пиріжки бідним (хоч один, хоч багато, хоч лише з будь-якого одного краю, хоч з обох, хоч взагалі не віддавати). Пиріжки, віддані бідним, вже не можна з'їсти, зате така дія дає можливість швидше дістатися до пиріжків, розміщених десь посередині. Дуже егоїстичного суб'єкта зовсім не цікавить, що саме дістанеться бідним, він лише намагається використати цей привід для максимізації суми смачностей пиріжків, які він з'їсть сам. Яку максимальну суму смачностей він може собі забезпечити?
Технічні умови Програма Pies читає з пристрою стандартного введення два цілих числа -- спочатку кількість пиріжків N (2<=N<=2019), потім відсоток щохвилинного погіршення смачностей K (1<=K<=50, ціле число), а далі в тому ж рядку рівно N чисел -- смачності пиріжків a1, a2, ..., aN, усі ці числа цілі, в межах від 1 до 123456789. Числа розділено пропусками. Програма виводить на пристрій стандартного виведення єдине дійсне число -- максимально можливу суму смачностей того, що може з'їсти дуже егоїстичний суб'єкт. Відповідь вважатиметься правильною, якщо АБСОЛЮТНА похибка не перевищуватиме 0,001.
Приклад
Введення
7 10 2 1 1 123456789 1 2 1
Виведення.
123456792.339
Примітка. Тут дуже вигідно з'їсти пиріжок смачності 123456789, поки він ще нічого не втратив, для чого на самому початку доводиться віддати бідним або всі три лівіші за нього, або всі три правіші; серед цих варіантів, краще віддати всі три правіші, бо три лівіших можуть дати суму смачностей 2*0.9+0.81+0.729 = 3.339, що більше, ніж максимально можлива для трьох правіших сума
0.9+2*0.81+0.729 = 3.249.