CF1874D Jellyfish and Miku

有 $n+1$ 个城市，编号从 $0$ 到 $n$，通过 $n$ 条道路连接。第 $i$ 条道路（$1 \leq i \leq n$）双向连接城市 $i-1$ 和城市 $i$。水母回到城市 $0$ 后，发现她把她的 Miku fufu 落在了城市 $n$。 每条道路都有一个正整数的美丽值。第 $i$ 条道路的美丽值为 $a_i$。 水母想要找回她的 fufu。由于她方向感很差，她不知道该往哪边走。每天，她会随机选择一条与当前城市相连的道路并通过它。设当前城市相连道路的美丽值之和为 $s$。对于每一条与当前城市相连的道路，水母会以概率 $\frac{x}{s}$ 通过美丽值为 $x$ 的这条道路，抵达另一端的城市。 水母从城市 $0$ 出发，只有到达城市 $n$ 时才能找回她的 fufu。 你需要选择每条道路的美丽值，使得水母期望找回 fufu 所需的天数最小。但由于经费有限，所有道路的美丽值之和不能超过 $m$。 请你求出在最优分配美丽值的情况下，水母期望找回 fufu 所需的最小天数。

输入仅一行，包含两个整数 $n$ 和 $m$（$1 \leq n \leq m \leq 3000$），分别表示道路数量和所有道路美丽值之和的最大值。

输出在最优分配美丽值的情况下，水母期望找回 fufu 所需的最小天数。 如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。形式化地，设你的答案为 $a$，标准答案为 $b$，当 $\frac{|a-b|}{\max(1,|b|)} \leq 10^{-9}$ 时，判为正确。

在第一个样例中，最优的美丽值分配为 $a=[1, 2, 5]$。水母期望找回 fufu 所需的天数为 $5.2$。 由 ChatGPT 4.1 翻译