CF489E Hiking

一个旅行者正在计划沿着河水进行一场水上远足。经过探测，他已经探明了这条河上适合晚上休息的$n$个地点，记录了这些地点与出发点的距离。 上述的每一个地点都有一个美丽度。也就是说，对于第$i$个地点，它和起点的距离为$x_i$，它的美丽度为$b_i$。 上述的每一个地点都在出发点的下游，且这个旅行者在旅行的时候只会顺流而下。 简言之，我们可以把河流看成一个数轴，出发点的坐标是$0$，第$i$个地点的坐标是$x_i$。旅行者只会沿正方向前进。 这个旅行者对他一天的前进距离，设定了一个基准值$l$，如果他某天的所前进的距离大于或小于了这个基准值，都会使他疲劳。假设他一天走了$r_i$的距离，那么他产生的疲劳值为$\sqrt{|r_j-l|}$，他整个旅程的总疲劳值为每一天的疲劳值之和。 显然，这个旅行者晚上需要休息，所以必须到达一个休息地点才能结束一天的行程，并在这个地点过夜。类似于上面的定义，假设他当天晚上在第$i$个地点休息，那么他当天的舒适度为这个地点的美丽度，即$b_i$。他整个旅程的总舒适度是每一天（包括最后一天）的舒适度之和。 现在他希望你帮助他规划旅游路线，确定出每一天在哪个地点休息，他对旅游的天数没有要求，但是要求最后一天必须在第$n$个地点休息。他希望你的这个规划足够合理，使得这次旅行的**总疲劳值除以总舒适度**的结果最小化。

无

无

$1\leq n \leq 1000$ $1\leq l \leq 10^5$ $1\leq x_i,b_i \leq10^6$ ### 样例解释 样例中总疲劳值除以总舒适度的最小值约为$0.097549$，即$(\frac{1+1+\sqrt 2 +0}{10+ 10+ 5+ 10})$