「生物」能量流动
题目描述
生物课上,小 F 学习到了食物链、食物网的相关内容。
他学到,能量是逐级递减的。比如在食物链上,两个链接起来的生物 $A \rightarrow B$(意思是 $B$ 吃 $A$)之间的能量传递效率最多只有 $\frac 1 5$;而研究种间关系,能够使能量流向对人类最有益的部分。
现在,小 F 想研究一下能量流动的关系,于是他在脑海里创造了一个生态的系统。
在这个生态的系统里,有 $n+2$ 种生物,其中 $0$ 是生产者,整个生态系统所流经的能量由它固定;你是贪婪的顶级掠食者 $n + 1$,可以捕食所有生物;其他的掠食者 $[1, n]$ 各有各的喜好,只会捕食编号在 $[0, r_i]$ 的生物。由于天然形成的强弱顺序,上述关系满足 $r_i \leq r_{i + 1}(1 \leq i < n),$ $r_i < i(1 \leq i \leq n)$。
每种动物需要摄取至少 $a_i$ 单位能量才能存活;一个生物摄取到的能量可以传递给捕食者,但传递效率都不超过 $\frac 1 5$。也就是说,假设该动物捕获了 $b_i$ 单位的能量,所有捕食它的掠食者得到的能量总和 $c_i$,那么有:
* $b_i \geq a_i$
* $c_i \leq \frac 1 5 b_i$
你希望知道,在所有生物都存活的情况下,在最优情况下你能获取到的最大能量是多少。
输入输出格式
输入格式
输入第一行两个整数 $n, a_0(1 \leq n \leq 10 ^ 5, 1 \leq a_0 \leq 10 ^ 9)$。$a_0$ 是生产者固定的能量值。
接下来 $n$ 行,每行 $2$ 个正整数,表示 $a_i, r_i(1 \leq a_i \leq 10 ^ 9)$。
数据保证,$0\leq r_i < i, r_i \leq r_{i + 1}$。
输出格式
输出一行一个浮点数,表示你——顶级掠食者——能得到的最大能量。如果不能使得所有生物存活(包括你自己),请输出 $-1$。
你的答案与参考答案的相对误差或者绝对误差不超过 $10 ^ {-8}$ 即被认为是正确的。如果你的程序是正确的,可以不用考虑精度问题。
输入输出样例
输入样例 #1
2 9
1 0
1 1
输出样例 #1
0.2000000
输入样例 #2
2 9
1 0
1 0
输出样例 #2
-1
输入样例 #3
2 10
1 0
1 0
输出样例 #3
0.4000000
说明
### 样例 1 解释
最优情况下:
* 1 号掠食者捕食生产者 0,捕食 5 点能量,传递效率为 $\frac 1 5$,得到 1 点能量。
* 2 号掠食者捕食生产者 0,捕食 4 点能量,传递效率为 $\frac 1 5$,得到 0.8 点能量。
* 2 号掠食者捕食掠食者 1,捕食 1 点能量,传递效率为 $\frac 1 5$,得到 0.2 点能量。
可怜的你只能捕获 2 号掠食者的能量,捕食 1 点能量,得到 0.2 点能量。
### 样例 2, 3 解释
由于 2 号掠食者开始减肥不吃肉了(也有可能是打不过 1 了),所以所需的生产者能量从 9 点变成了 10 点。
### 子任务
子任务 $1(21 \mathrm{pts}) : n \leq 100$;
子任务 $2(89 \mathrm{pts}) : n \leq 10 ^ 5$。