Mỗi dịp Giỗ Tổ Hùng Vương, dòng người từ khắp mọi miền đất nước lại cùng hướng về vùng đất linh thiêng để tưởng nhớ cội nguồn. Trải qua hàng nghìn năm lịch sử, hệ thống đường đi kết nối các vùng đã hình thành nên một mạng lưới rộng lớn, bao gồm cả những con đường cổ xưa lẫn các tuyến kết nối hiện đại.
Tuy nhiên, theo những ghi chép được lưu truyền qua nhiều thế hệ, hành trình tối ưu không chỉ phụ thuộc và khoảng cách địa lý mà còn chịu ảnh hưởng bởi một quy luật đặc biệt, được xác định bởi "mật mã năm" - một cơ chế cổ xưa dùng để định hướng con đường hiệu quả nhất.
Hệ thống giao thông được mô hình hoá thành một đồ thị vô hướng có trọng số gồm \(N\) đỉnh và \(M\) cạnh. Mỗi đỉnh biểu diễn một vùng đất, và mỗi cạnh biểu diễn một con đường hai chiều giữa hai vùng. Đỉnh thứ \(i\) có toạ độ \((x_i,y_i)\) trên mặt phẳng, và mỗi cạnh nối hai đỉnh \(u, v\) có chi phí di chuyển là \(w\).
Cho hai số nguyên dương \(n\) và \(Y\), trong đó \(n\) là mật mã và \(Y\) là năm hiện tại. Từ đó xác định:

• \(S\) : tổng các chữ số của \(n\)
• \(R\) : số đảo ngược của \(n\)
• \(A\) : tổng các chữ số của \(Y\)

Xét một điểm đặc biệt trên mặt phẳng:
\(\quad \quad \quad \quad \quad \quad x_0 = S + (A \bmod 100), \quad y_0 = (R + A) \bmod 10\)
Gọi \(T\) là đỉnh trong đồ thị có khoảng cách Euclid đến điểm \((x_0,y_0)\) là nhỏ nhất. Nếu có nhiều đỉnh thoả mãn, chọn đỉnh có chỉ số nhỏ nhất.
Đỉnh \(T\) chính là điểm đến cuối cùng của hành trình.

Do đặc thù của hệ thống đường cổ, tồn tại những vùng đất có khả năng "tăng tốc hành trình" nếu được lựa chọn đúng cách.

Bạn được phép chọn một đỉnh bất kỳ trên đường đi từ đỉnh \(1\) đến đỉnh \(T\) làm checkpoint.

• Khi hành trình đi qua checkpoint, một trạng thái đặc biệt được kích hoạt.
• Từ thời điểm kích hoạt thì: \(L\) cạnh tiếp theo trên đường đi sẽ có chi phí bằng \(\left\lfloor \frac{w}{2} \right\rfloor\). Nếu số cạnh còn lại nhỏ hơn \(L\), thì tất cả các cạnh còn lại đều được giảm.
• Trạng thái đặc biệt chỉ được kích hoạt đúng một lần.

Việc lựa chọn checkpoint có ảnh hưởng toàn cục đến kết quả cuối cùng và cần được tối ưu hoá cẩn thận.

Yêu cầu

Hãy xác định chi phí nhỏ nhất để đi từ đỉnh \(1\) đến đỉnh \(T\).

Input

• Dòng 1: ba số nguyên \(N,M\) \((1 \le N,M \le 10^4)\)
• Dòng 2: số nguyên \(n\) \((n \le 10^{18})\)
• Dòng 3: số nguyên \(Y\) \((1 \le Y \le 10^9)\)
• Dòng 4: số nguyên \(L\) \((1 \le L \le 100)\)
• \(N\) dòng tiếp theo: mỗi dòng gồm hai số thực \(x_i , y_i\) \((1 \le x_i , y_i \le 10^7)\)
• \(M\) dòng tiếp theo: mỗi dòng gồm ba số nguyên \(u,v,w\)

Output

• In ra một số nguyên duy nhất là chi phí nhỏ nhất.

Example

5 6
123
2024
1
0 0
2 1
4 1
6 1
8 1
1 2 4
2 3 4
3 4 4
4 5 4
1 3 4
2 5 20

10

Constraints

• Subtask 1 (50% số điểm):

  • \(1 \le N , M \le 10^3\).
  • \(1 \le n \le 10^{6}\)
  • \(1 \le Y , w \le 10^3\).
  • \(1 \le L \le 10\)

• Subtask 2 (50% số điểm):

  • \(1 \le N , M \le 10^4\)
  • \(1 \le n \le 10^{18}\)
  • \(1 \le Y , w \le 10^9\).
  • \(1 \le L \le 100\)