Темная Ассамблея — это такой орган управления в Преисподней. Здесь заседают сенаторы, которые принимают самые важные для игрока решения. Например, для расширения ассортимента магазина или для улучшения некоторых характеристик персонажа необходимо одобрение Темной Ассамблеи.

В Темную Ассамблею входит n сенаторов. Каждый из них характеризуется уровнем и лояльностью к игроку. Уровень — это некоторое целое положительное число, которое отражает силу сенатора. Лояльность — это вероятность принятия положительного решения при голосовании, которая измеряется в процентах с точностью до 10%.

Сенаторы принимают решения посредством голосования. Каждый из них принимает положительное или отрицательное решение в соответствии со своей лояльностью. Если строго больше половины сенаторов принимают положительное решение, то предложение игрока утверждается.

Если после голосования предложение игрока не утверждается, то игрок может опротестовать решение Темной Ассамблеи. Для этого нужно убить всех сенаторов, что проголосовали против (в убийстве сенаторов нет ничего страшного, они потом воскреснут и будут еще хуже относиться к игроку). Вероятность того, что игроку удастся убить некоторую группу сенаторов, равна A / (A + B), где A — сумма уровней всех персонажей игрока, а B — сумма уровней всех сенаторов в этой группе. Если игрок убивает всех неугодных сенаторов, то предложение игрока утверждается.

Сенаторы очень любят конфеты. Их можно подкупить, раздав им конфеты. За каждую полученную конфету сенатор увеличивает свою лояльность к игроку на 10%. Стоит учесть, что выше 100% лояльность подняться не может. Игрок может взять с собой в зал заседания не более k конфет. Конфеты следует раздать до начала голосования.

Определите вероятность того, что Темная Ассамблея одобрит предложение игрока при оптимальном распределении конфет между сенаторами.