406001: GYM102215 G Akinator

One day hacker Dmitry found an interesting game called Akinator. The rules of the game are very simple: player thinks of some famous person and Akinator tries to guess this person in a limited number of questions. Every turn Akinator asks player: «Is this person i₁ or i₂ or ... or i_m?» (here m is the number of people in the question, it can differ from question to question). The player answers «Yes» or «No», and Akinator will use obtained information. As soon as Akinator knows the thought person, he says the answer and wins. If Akinator can't guess the person in the given number of questions, he loses.

Akinator has k questions to guess the thought person. It is known in advance that Dmitry has thought of one of these n people: 1, 2, ..., n with the probabilities p₁, p₂, ..., p_n. Determine if Akinator can guarantee his guess in k questions, and if he can, what is the minimal average number of questions he needs for that.

First line contains two integers n and k (1 ≤ k ≤ n ≤ 100) — number of possibly thought persons and number of questions.

Second line contains n integers a₁, a₂, ... a_n (1 ≤ a_i ≤ 10¹²). Probabilities p_i are proportional to a_i, that is, they can be calculated as .

If Akinator can't surely guess the thought person, output «No solution».

Otherwise output the irreducible fraction — the minimal average number of questions Akinator needs to win the game.

4 1
8 1 9 2

No solution

4 2
1 2 3 4

2/1

4 3
1 2 3 4

19/10

In the third sample Akinator has 3 attempts. It is optimal to ask the first question about the 4th person. If the answer «No» is received, ask about the 3rd person. If the answer «No» is received here as well, use the last question to choose between 1st and 2nd persons.

The average number of attempts here is 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 1.9.