Dark Assembly

Dark Assembly is a governing body in the Netherworld. Here sit the senators who take the most important decisions for the player. For example, to expand the range of the shop or to improve certain characteristics of the character the Dark Assembly's approval is needed.

The Dark Assembly consists of n senators. Each of them is characterized by his level and loyalty to the player. The level is a positive integer which reflects a senator's strength. Loyalty is the probability of a positive decision in the voting, which is measured as a percentage with precision of up to 10%.

Senators make decisions by voting. Each of them makes a positive or negative decision in accordance with their loyalty. If strictly more than half of the senators take a positive decision, the player's proposal is approved.

If the player's proposal is not approved after the voting, then the player may appeal against the decision of the Dark Assembly. To do that, player needs to kill all the senators that voted against (there's nothing wrong in killing senators, they will resurrect later and will treat the player even worse). The probability that a player will be able to kill a certain group of senators is equal to A / (A + B), where A is the sum of levels of all player's characters and B is the sum of levels of all senators in this group. If the player kills all undesired senators, then his proposal is approved.

Senators are very fond of sweets. They can be bribed by giving them candies. For each received candy a senator increases his loyalty to the player by 10%. It's worth to mention that loyalty cannot exceed 100%. The player can take no more than k sweets to the courtroom. Candies should be given to the senators before the start of voting.

Determine the probability that the Dark Assembly approves the player's proposal if the candies are distributed among the senators in the optimal way.