#412. MJZ 的星系战争

MJZ 的星系战争

题目描述

今天,带恶人 MJZ 掀起了一场超大规模的星系战争,为了阻止疯狂的 MJZ,你需要前往 nn 个星球去招募勇士(为了部落!)。这些星球的编号为 1,2,...,n1, 2, ..., n ,地球(也就是你的初始所在)为 11 号星球。为了掩人耳目(?)你必须按照编号顺序依次访问这些星球,然后再回到地球上,也就是按照 $1 \rightarrow 2 \rightarrow ... \rightarrow n \rightarrow 1$ 的顺序访问。

当你驾驶飞船访问每个星球时,你的飞船都需要在星球上着陆然后再起飞,这两个过程都是需要耗费大量的燃料的。因为这是一艘神(zhi)奇(zhang)的飞船,它只在着陆和起飞时有大量消耗,至于在星球之间飞行所耗费的燃料,少到可以忽略不计。

对于编号为 ii 的星球,着陆所需的燃料为 M1/aiM_1 / a_i ,起飞所需的燃料为 M2/biM_2 / b_i ,其中 M1M_1M2M_2 分别表示着陆或起飞之前飞船的总重。飞船的总重可以表示为 M=m+fM = m + f ,其中 mm 表示飞船的净重, ff 表示飞船上当前搭载的燃料重量。

例如在编号为 ii 的星球上着陆之前有 m=9, f=3, ai=8, bi=2m = 9,\ f = 3,\ a_i = 8,\ b_i = 2 ,那么着陆需要 (9+3)/8=1.5(9 + 3) / 8 = 1.5 吨燃料,而起飞需要 (9+1.5)/2=5.25(9 + 1.5) / 2 = 5.25 吨燃料,因为着陆以后燃料被消费掉了,起飞之前 f=1.5f = 1.5 而不是 33

注意,整个过程是最开始从地球起飞,然后依次在 2,...,n2, ..., n 号星球着陆然后起飞,最后在地球着陆。

因为 MJZ 的军队已经将这些星球上的燃料掠夺一空,所以你没法在路上补充燃料,你的燃料只能在出发前全部装好。

同样是因为 MJZ 的军队的疯狂掠夺,现在燃料已经十分紧缺,你希望花费最少的燃料来完成招募任务。请计算访问这些星球并返回地球所需的最少燃料。上述所有重量的计数单位均相同。

输入格式

第一行两个正整数 nnmm ,表示星球个数和飞船净重。

接下来 nn 行,每行两个正整数 ai, bia_i,\ b_i ,分别表示每个星球的着陆参数和起飞参数,其作用如题目所述。

输出格式

输出一行一个浮点数表示答案。但是如果无论装载多少燃料都无法完成招募任务,则输出一个整数 1-1 不带浮点。

当答案的绝对值误差不超过 10410^{-4} 时即会被评测通过。

保证如果有解,则解小于101810^{18}

样例

样例输入

2 2
3 4
5 6

样例输出

4.000000

数据范围与提示

2n21052 \le n \le 2 · 10^5

1m, ai, bi1061 \le m,\ a_i,\ b_i \le 10^6