D. Stock
time limit per test
3 s
memory limit per test
512 megabytes
input
standard input
output
standard output

Xiao Ming dreamed that he bought a stock with an initial price of $$$v$$$ yuan, which then rose for $$$n$$$ consecutive trading days. Xiao Ming was so happy in his dream.

After waking up, Xiao Ming realized he could only remember whether the stock price increased by $$$x_i$$$ times or increased by $$$x_i$$$ yuan compared to the previous day for each of these $$$n$$$ trading days.

But Xiao Ming soon discovered a problem: rearranging these $$$n$$$ pieces of information could clearly make the average closing price of the stock over these $$$n$$$ trading days larger. Please help Xiao Ming rearrange the order of these $$$n$$$ pieces of information to maximize the average closing price after these $$$n$$$ trading days.

Formal problem statement:

There is a variable $$$v$$$ and $$$n$$$ operations, where the $$$i$$$-th operation is either $$$\times x_i$$$ or $$$+x_i$$$, and the operator is denoted as $$$\text{op}_i$$$.

You need to determine a permutation $$$p_1,...,p_n$$$ and compute $$$v_0=v,v_i=v_{i-1}\ \text{op}_{p_i}\ x_{p_i}$$$.

Maximize $$$\frac{v_1+v_2+...+v_n}{n}$$$.

Input

The first line contains $$$n,v$$$, representing the number of trading days and the initial stock price.

The next $$$n$$$ lines each contain $$$\text{op}_i\ x_i$$$, separated by a space, where $$$\text{op}_i$$$ must be either $$$+$$$ or $$$*$$$.

Input $$$n$$$ is an integer, $$$1\leq n\leq 30$$$.

Input $$$v,x_i$$$ are real numbers, accurate to six decimal places, $$$1\leq v\leq 10$$$;

For $$$\text{op}_i=+$$$, $$$0 \lt x_i \lt 1000$$$;

For $$$\text{op}_i=*$$$, $$$1 \lt x_i \lt 1.2$$$.

Output

Output a real number representing the final answer. Your answer will be considered correct if the absolute or relative error is less than $$$1\text{e}-9$$$.

That is, if the standard answer is $$$x$$$ and your output is $$$y$$$, it only needs to satisfy $$$\min (|x-y|,\frac{|x-y|}{x}) \lt 1\text{e}-9$$$.

Examples
Input
3 1.000000
+ 1.000000
* 1.100000
+ 0.100000
Output
2.1666666667
Input
5 1.000000
+ 1.000000
* 1.050000
* 1.100000
+ 0.100000
+ 0.500000
Output
2.6250000000