310710: CF1874D. Jellyfish and Miku

D. Jellyfish and Mikutime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

There are $n + 1$ cities with numbers from $0$ to $n$, connected by $n$ roads. The $i$-th $(1 \leq i \leq n)$ road connects city $i-1$ and city $i$ bi-directionally. After Jellyfish flew back to city $0$, she found out that she had left her Miku fufu in city $n$.

Each road has a positive integer level of beauty. Denote the beauty of the $i$-th road as $a_i$.

Jellyfish is trying to find her fufu. Because of her poor sense of direction, she doesn't know which way to go. Every day, she randomly chooses a road connected to the city she currently is in and traverses it. Let $s$ be the sum of the beauty of the roads connected to the current city. For each road connected to the current city, Jellyfish will traverse the road with a probability of $\frac x s$, where $x$ is the beauty of the road, reaching the city on the other side of the road.

Jellyfish will start at city $0$, and she will get only her fufu back when she reaches city $n$.

You want to choose the beauty of the roads such that the expected number of days Jellyfish takes to find her fufu will be the minimum possible. However, due to limited funding, the sum of beauties of all roads must be less than or equal to $m$.

Find the minimum expected number of days Jellyfish needs to get her fufu back if the beauty of the roads is chosen optimally.

Input

The first and only line of the input contains two integers $n$ and $m$ ($1 \leq n \leq m \leq 3000$) — the number of the roads and the maximum sum of beauty of the roads.

Output

Output the minimum expected number of days Jellyfish needs to get her fufu back if the beauty of the roads is chosen optimally.

Your answer will be accepted if the absolute or relative error does not exceed $10^{-9}$. Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is considered correct if $\frac{|a-b|}{\max(1,|b|)} \leq 10^{-9}$.

ExamplesInput

3 8

Output

5.200000000000

Input

10 98

Output

37.721155173329

Note

In the first example, the optimal assignment of beauty is $a=[1, 2, 5]$. The expected number of days Jellyfish needs to get her fufu back is $5.2$.

题目大意：
有从0到n编号的n+1个城市，通过n条道路相连。每条道路都有一个正整数的美丽度a_i。Jellyfish从城市0开始，每天随机选择一条与她所在城市相连的道路，并以其美丽度占总美丽度比例的概率穿过该道路。目标是使Jellyfish找到她的Miku fufu的期望天数最小，同时所有道路的美丽度之和不超过m。

输入数据格式：
第一行包含两个整数n和m（1≤n≤m≤3000）——道路的数量和道路美丽度的最大和。

输出数据格式：
输出Jellyfish找到她的Miku fufu的最小期望天数，如果道路的美丽度选择最优的话。如果绝对或相对误差不超过10^-9，则您的答案将被接受。

示例：
输入：3 8
输出：5.2

输入：10 98
输出：37.721155173329题目大意： 有从0到n编号的n+1个城市，通过n条道路相连。每条道路都有一个正整数的美丽度a_i。Jellyfish从城市0开始，每天随机选择一条与她所在城市相连的道路，并以其美丽度占总美丽度比例的概率穿过该道路。目标是使Jellyfish找到她的Miku fufu的期望天数最小，同时所有道路的美丽度之和不超过m。 输入数据格式： 第一行包含两个整数n和m（1≤n≤m≤3000）——道路的数量和道路美丽度的最大和。 输出数据格式： 输出Jellyfish找到她的Miku fufu的最小期望天数，如果道路的美丽度选择最优的话。如果绝对或相对误差不超过10^-9，则您的答案将被接受。 示例： 输入：3 8 输出：5.2 输入：10 98 输出：37.721155173329