310233: CF1801F. Another n-dimensional chocolate bar

F. Another n-dimensional chocolate bartime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output Mom bought the boy Vasya a $n$-dimensional chocolate bar, which is a $n$-dimensional cube with the length of each side equal to $1$. The chocolate is planned to be divided into slices. According to the $i$th dimension, it can be divided by hyperplanes into $a_i$ equal parts. Thus, the chocolate is divided in total into $a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n$ slices, each slice has a length of $i$-th dimension equal to $\frac{1}{a_i}$, respectively, the volume of each slice is $\frac{1}{a_1 a_2 \cdots a_n}$.

Vasya and his friends want to cut a chocolate bar to get at least $k$ pieces, while Vasya wants to maximize the volume of the smallest of them. It is possible to cut the chocolate bar only at the junction of the lobules, and each incision must pass through the entire chocolate bar along some hyperplane involved in the formation of lobules. Only after making all the cuts, Vasya disassembles the chocolate into pieces.

More formally, Vasya wants to choose the numbers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le a_i$) — the number of parts into which Vasya will cut the chocolate bar along each dimension. The condition $b_1 \cdot b_2 \cdot \ldots \cdot b_n \ge k$ must be met to get at least $k$ pieces after all cuts. It can be noted that with optimal cutting with such parameters, the minimum piece will contain $\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor$ slices, and its volume will be equal to $\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor \cdot \frac{1}{a_1 a_2 \cdots a_n}$.

Vasya wants to get the maximum possible value of the volume of the minimum piece multiplied by $k$, that is, he wants to maximize the number of $\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor \cdot \frac{1}{a_1 a_2 \cdots a_n} \cdot k$. Help him with this.

Input

The first line contains two integers $n$ and $k$ $(1 \le n \le 100$, $1 \le k \le 10^7)$ — the dimension of the chocolate bar, and how many parts it needs to be divided into.

The second line contains $n$ integers $a_1,\ a_2,\ \dots,\ a_n$ $(1 \le a_i \le 10^7)$ — the number of pieces on which the chocolate is placed along each of the dimensions.

Output

Print one number  — the maximum possible volume of the smallest of the obtained pieces, multiplied by $k$, with an absolute or relative error of no more than $10^{-9}$.

If it is impossible to cut a chocolate bar into at least $k$ pieces under the given restrictions, output $0$.

Examples

Input

1 2
5

Output

0.8

Input

2 6
5 10

Output

0.72

Input

2 7
4 4

Output

0.875

Input

2 3
4 5

Output

0.75

Input

4 444
57 179 239 2

Output

0.97557326850704739751

Input

2 5
2 2

Output

0

Note

In the first example, a one – dimensional chocolate bar can be divided as follows:

Then the answer will be $\frac{2}{5} \cdot 2 = 0.8$

In the second example, the chocolate bar can be cut as follows:

Then the answer will be $\frac{2}{5} \cdot \frac{3}{10} \cdot 6 = 0.72$

In the third example, the chocolate bar can be cut as follows:

Then the answer will be $\frac{2}{4} \cdot \frac{1}{4} \cdot 7 = 0.875$

题目大意：
妈妈给瓦西亚买了一块n维巧克力，它是一个边长为1的n维立方体。巧克力计划被切成片。在第i维上，它可以被超平面切成a_i个等分。因此，巧克力总共被切成a_1 * a_2 * a_3 * ... * a_n片，每片的第i维长度分别为1/a_i，相应地，每片的体积为1/(a_1 * a_2 * ... * a_n)。

瓦西亚和他的朋友们想要切一块巧克力，得到至少k块，同时瓦西亚想要最大化最小块的体积。只能在巧克力块之间的接合处切割，并且每一切割都必须沿着某个参与形成块的超平面穿过整个巧克力块。只有在完成所有切割后，瓦西亚才会将巧克力拆分成块。

更正式地说，瓦西亚想要选择数字b_1, b_2, ..., b_n（1 <= b_i <= a_i）——瓦西亚将沿着每个维度切割巧克力块的部件数。必须满足条件b_1 * b_2 * ... * b_n >= k，才能在所有切割后至少得到k块。可以注意到，在具有此类参数的最优切割下，最小块将包含⌊a_1/b_1⌋...⌊a_n/b_n⌋片，其体积将等于⌊a_1/b_1⌋...⌊a_n/b_n⌋ * 1/(a_1 * a_2 * ... * a_n)。

瓦西亚想要得到最小块体积乘以k的最大可能值，即他想要最大化⌊a_1/b_1⌋...⌊a_n/b_n⌋ * 1/(a_1 * a_2 * ... * a_n) * k的数目。帮助他做到这一点。

输入输出数据格式：
输入：
第一行包含两个整数n和k（1 <= n <= 100，1 <= k <= 10^7）——巧克力块的维度，以及需要将其分割成的部分数。
第二行包含n个整数a_1, a_2, ..., a_n（1 <= a_i <= 10^7）——沿着每个维度放置巧克力的部分数。

输出：
打印一个数字——在给定限制下，得到的最小块的最大可能体积乘以k，绝对或相对误差不超过10^-9。

如果根据给定的限制，无法将巧克力块切成至少k块，则输出0。题目大意： 妈妈给瓦西亚买了一块n维巧克力，它是一个边长为1的n维立方体。巧克力计划被切成片。在第i维上，它可以被超平面切成a_i个等分。因此，巧克力总共被切成a_1 * a_2 * a_3 * ... * a_n片，每片的第i维长度分别为1/a_i，相应地，每片的体积为1/(a_1 * a_2 * ... * a_n)。 瓦西亚和他的朋友们想要切一块巧克力，得到至少k块，同时瓦西亚想要最大化最小块的体积。只能在巧克力块之间的接合处切割，并且每一切割都必须沿着某个参与形成块的超平面穿过整个巧克力块。只有在完成所有切割后，瓦西亚才会将巧克力拆分成块。 更正式地说，瓦西亚想要选择数字b_1, b_2, ..., b_n（1 <= b_i <= a_i）——瓦西亚将沿着每个维度切割巧克力块的部件数。必须满足条件b_1 * b_2 * ... * b_n >= k，才能在所有切割后至少得到k块。可以注意到，在具有此类参数的最优切割下，最小块将包含⌊a_1/b_1⌋...⌊a_n/b_n⌋片，其体积将等于⌊a_1/b_1⌋...⌊a_n/b_n⌋ * 1/(a_1 * a_2 * ... * a_n)。 瓦西亚想要得到最小块体积乘以k的最大可能值，即他想要最大化⌊a_1/b_1⌋...⌊a_n/b_n⌋ * 1/(a_1 * a_2 * ... * a_n) * k的数目。帮助他做到这一点。 输入输出数据格式： 输入： 第一行包含两个整数n和k（1 <= n <= 100，1 <= k <= 10^7）——巧克力块的维度，以及需要将其分割成的部分数。 第二行包含n个整数a_1, a_2, ..., a_n（1 <= a_i <= 10^7）——沿着每个维度放置巧克力的部分数。 输出： 打印一个数字——在给定限制下，得到的最小块的最大可能体积乘以k，绝对或相对误差不超过10^-9。 如果根据给定的限制，无法将巧克力块切成至少k块，则输出0。