Best Coalitions#781

Best Coalitions

1 second

64 megabytes

Medium

Envy Inc. is a joint-stock company, where each stockholder legally owns a percentage of the total shares. Due to the global economic crisis, the management rules of Envy Inc. define a special way for distributing last year's profit: if a stockholder owns more than half of the shares, he or she receives the total profit. This is nothing unusual in today's business world!

However, if no stockholder owns more than $50%$ of the shares, stockholders are allowed to form coalitions, i.e., groups of stockholders. The coalition's participation percentage is the sum of its members' share percentages. If a coalition owns more than half the shares, its members receive the total profit, distributed proportionally to each member's participation in the coalition.

For example, suppose there are $5$ stockholders: $A$ , $B$ , $C$ , $D$ , and $E$ , who own $20%$ , $12%$ , $14%$ , $29%$ , and $25%$ of the company shares, respectively. Stockholder $E$ can form several winning coalitions. For instance, if $E$ forms a coalition with $A$ and $B$ , $E$ receives $43.86%$ of the profit. If $E$ forms a coalition with $B$ and $C$ instead, $E$ receives $49.02%$ . On the other hand, $E$ cannot form a winning coalition with only $A$ .

Your task is, given a distribution of shares in Envy Inc. and a specified stockholder, to determine the maximum percentage of last year's profit the selected stockholder can receive.

Input

The input consists of several test cases. Each test case specifies a distribution of share percentages and an index for a stockholder for whom the optimal participation must be determined. Each test case consists of several lines:

The first line contains two integers $n$ ( $1 \leq n \leq 100$ 1 \leq n \leq 100) and $x$ ( $1 \leq x \leq n$ 1 \leq x \leq n), separated by a space. $n$ is the number of stockholders in Envy Inc., and $x$ is the index of the stockholder to analyze.
Each of the next $n$ lines contains a single floating point value $p_{i}$ p_i, rounded to two decimal places, representing the percentage of shares owned by stockholder $i$ ( $1 \leq i \leq n$ 1 \leq i \leq n). The decimal separator is " $.$ " (a dot). You may assume $p_{1} + \dots + p_{n} = 100$ p_1 + \ldots + p_n = 100.

The end of input is signaled by $n = x = 0$ n = x = 0, which should be ignored.

Output

For each test case, output a single line with the corresponding answer. The answer must be formatted and rounded to two decimal places. The decimal separator must be " $.$ " (a dot). Round to the nearest neighbor; if both neighbors are equidistant, round up (for example, $78.312 \to 78.31$ 78.312 \to 78.31; $78.566 \to 78.57$ 78.566 \to 78.57; $78.345 \to 78.35$ 78.345 \to 78.35, etc.).

Examples

Example 1