Electric Vehicle

An electric vehicle (EV) is an alternative fuel automobile that uses one or more electric motors for propulsion, in place of an internal combustion engine such as a diesel or gasoline engine. The EV stores electricity in an energy storage device, such as a battery, and the electricity powers the vehicle's wheels through electric motors. Its energy storage capacity is limited, so the EV must be recharged regularly by plugging into an electrical source.

There are $n$ villages, referred to as points on a plane. For any two villages, there is exactly one road between them, so there are $n \times (n-1)/2$ roads in total. Let two villages $A$ and $B$ have coordinates $(a, b)$ and $(c, d)$. The length of the road between them is $d(A, B) = |a-c| + |b-d|$, which is called the distance between $A$ and $B$. For convenience, the distance between $A$ and $B$ equals the amount of electricity an EV needs to move between them. That is, while an EV consumes electricity 1, it can move distance 1.

Each village has a charging station for an EV, and the charging cost varies from village to village. Let $c(A)$ be the cost per unit of electricity when an EV is charged in village $A$. An EV with zero charge at village $A$ must be charged at a cost of at least $c(A) \cdot d(A, B)$ in $A$ to reach village $B$.

Minsu must travel from village $S$ to village $T$ in his EV. The EV is discharged, with zero charge, at $S$ before departure. The battery has a maximum charge capacity $W$, so the EV cannot store more than $W$ units of electricity. A fully charged EV can move a distance of $W$. On the way from $S$ to $T$, Minsu may make at most $\Delta$ stops for recharging. Charging at the starting village $S$ counts as one of these stops. Find the cheapest way for Minsu to travel from $S$ to $T$.

The first line contains an integer $n$ ($2 \le n \le 1{,}000$), the number of villages. Each of the next $n$ lines contains three integers $a$, $b$, and $c$ ($0 \le a, b \le 10^6$ and $1 \le c \le 10^4$), where $(a, b)$ is the coordinate of a village and $c$ is the charging cost at that village. The first of these lines gives the starting village $S$, and the second gives the destination $T$. All village coordinates are distinct. The next line contains an integer $W$ ($1 \le W \le 10^5$), the maximum charge capacity of the battery. The last line contains a positive integer $\Delta$ ($1 \le \Delta \le 10$), the maximum number of times the EV may recharge during the trip from $S$ to $T$. Charging at $S$ counts as one of these stops.

Print exactly one line containing the cost of the cheapest way for the EV to travel from $S$ to $T$ with at most $\Delta$ stops for recharging. If no such way exists, print -1.