电动汽车（EV）是一种使用一个或多个电动机作为动力源的替代燃料汽车，取代了柴油或汽油等内燃机。电动汽车将电能存储在能量存储设备（如电池）中，并通过电动机为车辆的轮子提供动力。由于其有限的能量存储容量，电动汽车必须通过接入电源进行定期充电。

平面上有 $n$ 个村庄。任意两个村庄之间只有一条道路。因此，连接各个村庄的道路总数恰好为 $n \times (n - 1) / 2$ 条。设两个村庄 $A$ 和 $B$ 的坐标分别为 $(a, b)$ 和 $(c, d)$。则 $A$ 和 $B$ 之间的道路长度定义为 $d(A, B) = |a - c| + |b - d|$，这被称为 $A$ 和 $B$ 之间的距离。为方便起见，假设 $A$ 和 $B$ 之间的距离等同于电动汽车在 $A$ 和 $B$ 之间移动所需的电量。也就是说，电动汽车消耗单位电量（例如电量 1）可以移动单位距离（例如距离 1）。

每个村庄都有一个电动汽车充电站，充电成本因村庄而异。设 $c(A)$ 为在村庄 $A$ 充电时每单位电量的成本。根据上述假设，在村庄 $A$ 电量为零的电动汽车，若要到达村庄 $B$，必须支付至少 $c(A) \times d(A, B)$ 的费用。

民秀（Minsu）需要驾驶他的电动汽车从村庄 $S$ 前往村庄 $T$。出发前，电动汽车在 $S$ 处处于放电状态，即电量为零。此外，电动汽车的电池最大充电容量为 $W$。也就是说，电动汽车存储的电量不能超过 $W$。因此，如果电动汽车充满电，它最多可以移动距离 $W$。在从 $S$ 到 $T$ 的途中，民秀最多允许进行 $\Delta$ 次充电停靠。此外，在起始村庄 $S$ 的充电也被视为一次充电停靠。民秀需要找到从 $S$ 到 $T$ 的最便宜移动方式。

例如，上图显示了平面上的五个村庄，五边形中的数字代表充电成本。设 $W = 3$ 且 $\Delta = 2$。图中展示了从 $S$ 到 $T$ 的三种路径 $P_1, P_2$ 和 $P_3$，分别用红色、紫色和蓝色表示。在 $P_1$ 中，电动汽车在 $S$ 处充电电量 2，并在 $(1, 3)$ 处再次充电电量 2。因此，总共花费 $2 \times 4 + 2 \times 4 = 16$。对于 $P_2$ 的情况，电动汽车在 $S$ 处充满电，到达 $(2, 2)$ 时电池中剩余电量 1。然后电动汽车在 $(2, 2)$ 处仅充电电量 1 以到达 $T$。因此，总共花费 $3 \times 4 + 1 \times 5 = 17$。最后，在 $P_3$ 中，电动汽车在 $S$ 处充电电量 2 以移动到 $(3, 1)$，并在 $(3, 1)$ 处再次充电电量 2。因此，总共花费 $2 \times 4 + 2 \times 3 = 14$。成本 14 是最小值，$P_3$ 是从 $S$ 到 $T$ 最便宜的路径。

给定包含 $S$ 和 $T$ 在内的 $n$ 个村庄的坐标、每个村庄的充电成本、电动汽车电池的最大充电容量 $W$ 以及任意正整数 $\Delta$，编写一个程序，找出在最多 $\Delta$ 次充电停靠的情况下，从 $S$ 到 $T$ 的最便宜移动方式。

输入格式

程序从标准输入读取数据。输入以一个整数 $n$ ($2 \le n \le 1,000$) 开头，表示村庄的数量。接下来的 $n$ 行，每行包含三个整数 $a, b$ 和 $c$ ($0 \le a, b \le 10^6$ 且 $1 \le c \le 10^4$)，其中 $(a, b)$ 是村庄的坐标，$c$ 是该村庄的充电成本。这里，在 $n$ 行中，第一行包含起始村庄 $S$ 的坐标，第二行包含目的地村庄 $T$ 的坐标。注意，所有村庄的坐标都是不同的。下一行包含一个整数 $W$ ($1 \le W \le 10^5$)，表示电动汽车电池的最大充电容量。最后一行包含一个正整数 $\Delta$ ($1 \le \Delta \le 10$)，表示电动汽车从 $S$ 到 $T$ 行驶过程中允许的最大充电次数。在起始村庄 $S$ 的充电被视为一次充电停靠。

输出格式

程序将结果写入标准输出。仅打印一行。该行应包含电动汽车在最多 $\Delta$ 次充电停靠的情况下从 $S$ 到 $T$ 的最便宜移动成本。如果不存在这样的路径，则该行应包含 -1。

样例

样例输入 1

4
0 0 1
3 0 3
1 0 3
2 0 3
4
2

样例输出 1

3

样例输入 2

5
1 1 4
3 3 3
1 3 4
2 2 5
3 1 3
3
2

样例输出 2

14

样例输入 3

5
1 1 4
3 3 3
1 3 4
2 2 5
3 1 3
3
1

样例输出 3

-1