6498：跨洋飞行

大多数人都在享受安逸生活的日子里，有些人，正在冒着生命危险，在大海航行，在天空漂泊。在他们心中，有着和生命同等重要的东西，他们追寻着梦想的指引，不断挑战自己的极限，只是为了见到，比远方更远的那缕曙光。



张博，一个企业家。



那一年，52岁的他get了一个新技能：

开小飞机。 在那些阴郁的冬天，厚厚的云层压得人喘不过气来。于是就驾驶飞机带着朋友飞到芝加哥的云层上方，享受几个小时难得阳光。就是那样一种可以同时看见天空与大地的飞行。



转眼，2016年的8月来了。

54岁的他跳进了飞机的驾驶舱。

开启了一段披星戴月的连续飞行。

每天每天，很早起飞，很晚降落。

每天每天，都不敢离开地平线太远。

因为一旦看不到地平线。

很可能再也没有下一次飞行。

49天后，平安归来。

他绕着地球飞了一圈。



转眼，2019年的4月来了。57岁的他又跳进了飞机的驾驶舱。

此刻，张博博士正在从大洋彼岸飞来的路上，

这一次几十天的旅途，只为一个目的——

飞到2050，与全世界的年青人团聚三天。



张博博士正翱翔在广袤的大洋上空。

已知地图上一共有 $n$ 个机场，张博博士要从 $1$ 号机场飞到 $n$ 号机场，也就是2050的举办地杭州。

从 $i$ 号机场飞行到 $j$ 号机场需要消耗 $dist(i,j)$ 个单位的油量，其中 $dist(i,j)$ 为 $i$ 号机场和 $j$ 号机场之间的欧几里得距离。

张博博士可以选择在任意机场起降和加油。飞机油箱最多可以保存 $u$ 单位的燃油。

考虑到可能遇到的极端天气，某些机场在某些时候不具备降落的条件。所以出于安全的考虑，当他飞到一个机场的时候，必须保证飞机剩下的油足以飞到离他最近的机场。

假设一次起飞和降落分别需要花费 $a$ 秒和 $b$ 秒的时间，加 $1$ 单位的油需要花费 $c$ 秒的时间，飞行 $1$ 单位的距离需要花费 $d$ 秒的时间，请问张博博士最早什么时候可以到达杭州，和我们相见？

飞机初始的油量为0，也就是说，飞机需要先在起点加油再起飞。

第一行一个整数 $T~(1\leq T\leq 50)$，表示数据组数。

对于每组数据：

第一行 $6$ 个整数 $n,a,b,c,d,u~(2\leq n\leq 10^3,0\leq a,b,c,d,u\leq 10^5)$。

接下来 $n$ 行，每行两个整数 $x_i,y_i~(0\leq x_i, y_i\leq 10^5)$ 表示第 $i$ 个机场的坐标。

对于每组数据输出一行一个数，表示最早的到达时间，只要你的答案和标准答案相对误差或者绝对误差在 $10^{-5}$ 以内就算通过。

数据保证有解。