Một xe chạy bằng điện EV mới được sử dụng thay thế cho các xe nhiên liệu truyền thống. Có \(n\) thành phố trên một mặt phẳng, với hai thành phố bất kì sẽ có một con đường nồi chúng. Giả sử hai thành phố \(A\) và \(B\) có tọa độ là \((a, b)\) và \((c, d)\) thì khoảng cách giữa hai thành phố này \(d(A, B) = |a - c| + |b - d|\). Để dễ hình dung, ta coi mỗi đơn vị di chuyển EV sẽ tiêu tốn đúng 1 đơn vị nhiêu liệu điện. Mỗi thành phố có một trạm nạp điện cho xe, thành phố \(A\) sẽ có chi phí \(c(A)\) cho một đơn vị nhiên liệu điện. Nếu xe EV tại thành phố A đang không có đơn vị nhiên liệu nào muốn di chuyển đến thành phố \(B\) thì nó phải mất chi phí nhỏ nhất là \(c(A)\times d(A, B)\) để có thể di chuyển từ \(A\) đến \(B\).

ATM phải di chuyển từ thành phố \(S\) đến thành phố \(T\) bằng xe EV của anh ấy. Ban đầu chiếc xe này đang không có nhiên liệu nào. Và chiếc xe này có thể nạp đầy được \(W\) nhiên liệu hay chiếc EV này không thể chứa nhiều hơn \(W\) nhiện liệu một lúc. Do đó nó không thể di chuyển được giữa hai thành phố có khoảng cách lớn hơn \(W\). Ngoài ra ATM chỉ cho phép nạp tối đa \(p\) lần nạp điện kể cả lần nạp đầu tiên.

Cho biết tọa độ của \(n\) thành phố và \(S, T\), chi phí nạp nhiên liệu tại mỗi thành phố, \(W\) và \(p\), hãy tính chi phí nhỏ nhất để có thể đi được từ \(S\) đến \(T\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 < n\le 1000\)).
• \(n\) dòng tiếp theo mỗi dòng chứa 3 số nguyên \(a, b, c\) là tọa độ và chi phí của các thành phố (\(0\le a, b\le 10^6, 1\le c\le 10^4\)). Trong đó dòng đầu tiên là thành phố \(S\), dòng thứ hai là thành phố \(T\).
• Tiếp theo chứa số nguyên \(W\) (\(1\le W\le 10^5\)).
• Dòng cuối cùng chứa số nguyên \(p\) (\(1\le p\le 10\)).

Output

• Ghi ra chi phí nhỏ nhất, hoặc ghi ra -1 nếu không thể đi được từ \(S\) đến \(T\).

Example

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

14

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

-1

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

3