Имеется $$$n + 1$$$ городов с номерами от $$$0$$$ до $$$n$$$, соединенные $$$n$$$ дорогами. Дорога $$$i$$$-го города $$$(1 \leq i \leq n)$$$ соединяет города $$$i-1$$$ и $$$i$$$ двунаправленно. После того, как Медуза прилетела обратно в город $$$0$$$, она обнаружила, что оставила свою фуфу Мику в городе $$$n$$$.

Каждая дорога имеет целый положительный уровень красоты. Обозначим красоту $$$i$$$-й дороги как $$$a_i$$$.

Медуза пытается найти свою фуфу. Из-за плохого чувства направления она не знает, в какую сторону идти. Каждый день она наугад выбирает дорогу, связанную с городом, в котором находится в данный момент, и идет по ней. Пусть $$$s$$$ — сумма красот дорог, ведущих в текущий город. Для каждой дороги, связанной с текущим городом, Медуза пройдет ее с вероятностью $$$\frac x s$$$, где $$$x$$$ — красота дороги, и достигнет города, расположенного на другом конце дороги.

Медуза стартует из города $$$0$$$, и, только достигнув города $$$n$$$, она может воссоединиться со своей фуфу.

Вы хотите выбрать такую красоту дорог, чтобы ожидаемое количество дней, которые потребуются Медузе для поиска своей фуфу, было минимально возможным. Однако из-за ограниченного финансирования сумма красот всех дорог должна быть меньше или равна $$$m$$$.

Найдите минимальное ожидаемое количество дней, которое потребуется Медузе для возвращения своей фуфу, если красота дорог выбрана оптимально.