Cho đồ thị \(n\) đỉnh, các đỉnh đánh số từ 1 đến \(n\). Có \(m\) cặp đỉnh không thể đi chuyển trực tiếp đến nhau. Mỗi đỉnh \(u\) có một trọng số \(w_u\). Chi phí di chuyển từ đỉnh \(u\) đến đỉnh \(v\) là \(|w_u-w_v |\). Cho phép thay đổi trọng số của không quá \(k\) đỉnh \(u\) mà \(1<u<n\).

Yêu cầu:

• Hãy tìm đường đi có chi phí nhỏ nhất từ 1 đến \(n\) khi đã thay đổi trọng số của không quá \(k\) đỉnh.

Input

• Dòng đầu chứa \(n,m,k (2≤n≤500;0≤m≤n(n-1)/2;0≤k≤n-2)\)

• Dòng thứ hai chứa \(n\) số \(w_1,w_2,..,w_n (0≤w_i≤10^9)\)

• \(m\) dòng tiếp theo, mỗi dòng chứa hai số \(u,v (1≤u≠v≤n)\) mô tả các cặp đỉnh không di chuyển trực tiếp được đến nhau.

Output

• Ghi ra một số là chi phí nhỏ nhất tìm được. Nếu không thể di chuyển từ 1 đến n thì in ra −1.

Ràng buộc

• Subtask 1: (20%): \(k=0\)

• Subtask 2: (30%): \(k=1\)

• Subtask 3: (50%): không có ràng buộc gì thêm

Sample Input

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

Sample Output

11

Sample Input

4 3 1
1 7 4 2
1 3
1 4
2 4

Sample Output

5

Sample Input

4 3 3
1 7 4 2
1 3
1 4
2 4

Sample Output

1