전기 자동차

전기 자동차(EV)는 디젤 엔진이나 가솔린 엔진 같은 내연기관 대신 하나 이상의 전기 모터로 추진하는 대체 연료 자동차이다. EV는 배터리 같은 에너지 저장 장치에 전기를 저장하고, 그 전기가 전기 모터를 거쳐 바퀴를 구동한다. 저장 용량이 제한되어 있어서 EV는 전원에 연결해 주기적으로 충전해야 한다.

평면 위에 $n$개의 마을이 있다. 임의의 두 마을 사이에는 도로가 정확히 하나씩 있으므로, 도로는 모두 $n \times (n-1)/2$개이다. 마을 $A$와 $B$의 좌표를 각각 $(a, b)$, $(c, d)$라 하자. 두 마을 사이 도로의 길이는 $d(A, B) = |a-c| + |b-d|$로 정의하며, 이를 $A$와 $B$의 거리라고 부른다. 편의상 $A$와 $B$의 거리는 EV가 둘 사이를 이동하는 데 필요한 전기량과 같다고 가정한다. 즉 EV가 전기 1을 소비하면 거리 1을 이동할 수 있다.

각 마을에는 EV 충전소가 있으며, 충전 비용은 마을마다 다를 수 있다. $c(A)$를 마을 $A$에서 EV를 충전할 때 전기 1당 비용이라 하자. 충전량이 0인 EV는 $A$에서 $B$까지 가려면 $A$에서 적어도 $c(A)d(A, B)$의 비용으로 충전해야 한다.

민수는 EV를 타고 마을 $S$에서 마을 $T$까지 가야 한다. EV는 출발 전 $S$에서 충전량이 0인 상태이다. 배터리의 최대 충전 용량은 $W$이므로 EV는 $W$를 넘는 전기를 저장할 수 없다. 가득 충전된 EV는 거리 $W$를 이동할 수 있다. 민수는 $S$에서 $T$까지 가는 동안 충전을 위해 최대 $\Delta$번 멈출 수 있다. 출발지 $S$에서의 충전도 이 멈춤 중 하나로 센다. 민수가 $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$는 그 마을의 충전 비용이다. 첫 줄은 출발 마을 $S$, 둘째 줄은 도착 마을 $T$를 나타낸다. 모든 마을의 좌표는 서로 다르다. 다음 줄에는 배터리의 최대 충전 용량 $W$ ($1 \le W \le 10^5$)가 주어진다. 마지막 줄에는 양의 정수 $\Delta$ ($1 \le \Delta \le 10$)가 주어지며, 이는 $S$에서 $T$까지 이동하는 동안 충전할 수 있는 최대 횟수이다. 출발 마을 $S$에서의 충전도 이 횟수에 포함된다.

충전을 최대 $\Delta$번까지 하면서 EV가 $S$에서 $T$까지 이동하는 가장 저렴한 방법의 비용을 한 줄에 출력한다. 그런 방법이 없으면 -1을 출력한다.