P1132

[Sdoi2008]Sue的小球

[Sdoi2008]Sue的小球

Sue 和 Sandy 最近迷上了一款电脑游戏。游戏的故事发生在美丽、神秘而又充满刺激的大海上,Sue 驾驶着一艘轻便小巧的船,收集漂浮在空中的彩蛋。

Sue 有一个秘密武器:只要将船移动到某个彩蛋的正下方,就可以瞬间收集这个彩蛋。每个彩蛋都有魅力值,其魅力值会随着彩蛋在空中下落的时间而降低。为了获得更多分数,Sue 需要尽量在彩蛋的魅力值较高时将其收集。如果彩蛋掉入海中,它的魅力值会变成负数,但这并不影响 Sue 收集它,因为每个彩蛋都是独一无二的,Sue 希望收集所有彩蛋。

然而,Sandy 更关心得到尽可能高的分数。为了解决这个问题,他将游戏抽象成如下模型:

以 Sue 初始位置所在的水平面作为 xx 轴。初始时,空中共有 NN 个彩蛋。第 ii 个彩蛋的初始位置为整数坐标 (xi,yi)(x_i,y_i)。游戏开始后,它以每单位时间 viv_i 个单位距离的速度,沿 yy 轴负方向匀速下落。

Sue 的初始位置为 (x0,0)(x_0,0),可以沿 xx 轴正方向或负方向移动,移动速度为每单位时间 11 个单位距离。使用秘密武器收集彩蛋不需要时间,收集一个彩蛋所得的分数为该彩蛋当前 yy 坐标的 1/10001/1000。

请在收集所有彩蛋的前提下,使 Sue 得到的总分最高。

输入格式

第一行包含两个整数 N,x0N,x_0,分别表示彩蛋数量和 Sue 的初始横坐标。

第二行包含 NN 个整数 xix_i,其中第 ii 个整数表示第 ii 个彩蛋的初始横坐标。

第三行包含 NN 个整数 yiy_i,其中第 ii 个整数表示第 ii 个彩蛋的初始纵坐标。

第四行包含 NN 个整数 viv_i,其中第 ii 个整数表示第 ii 个彩蛋沿 yy 轴负方向匀速下落的速度。

输出格式

输出一个实数,表示在收集所有彩蛋的前提下能够得到的最高总分,保留 33 位小数。

样例输入

3 0
-4 -2 2
22 30 26
1 9 8

样例输出

0.000

数据范围

  • 1≤N≤1031\le N\le 10^3;
  • −104≤x0,xi≤104-10^4\le x_0,x_i\le 10^4;
  • 0≤yi≤1050\le y_i\le 10^5;
  • 1≤vi≤1041\le v_i\le 10^4。

来源与许可

本题为 SDOI 2008 试题「Sue 的小球」,题面与测试数据整理自 BZOJ。

样例 1

输入

3 0
-4 -2 2
22 30 26
1 9 8

输出

0.000