Sau kì thi học sinh giỏi, Việt đi du lịch ở thành phố HP - nơi có ~n~ địa điểm du lịch được đánh số từ ~1~ đến ~n~, giá vé của mỗi địa điểm là ~c_i~ (~i = 1 \div n~). Có ~m~ con đường 2 chiều, mỗi con đường kết nối 2 địa điểm du lịch ~u~ và ~v~ (~1 \le u, v \le n; u \ne v~). Ban quản lý lập danh sách các tour du lịch, mỗi tour gồm tất cả các địa điểm có đường đi trực tiếp hoặc gián tiếp đến nhau. Chi phí một tour bằng tổng tiền vé của các địa điểm trong tour.

Là người thích trải nghiệm đến nhiều vùng khác nhau nên Việt chọn ~k~ tour du lịch và quan tâm đến độ chênh lệch chi phí nhỏ nhất của 2 tour bất kì trong ~k~ tour. Việt muốn tính giá trị tối đa của độ chênh lệch chi phí nhỏ nhất trong các cách chọn ~k~ tour.

Yêu cầu: Hãy giúp Việt tính giá trị tối đa trên.

Input

• Dòng đầu tiên có 3 số nguyên dương ~n, m, k~ (~n, m, k \le 10^5~);
• Dòng thứ hai có ~n~ số nguyên dương ~c_1, c_2, \dots, c_n~ (~c_i \le 10^9, \forall i = 1 \div n~) là giá vé du lịch của các địa điểm;
• ~m~ dòng tiếp theo, mỗi dòng có 2 số nguyên dương ~u~ và ~v~ mô tả có một con đường 2 chiều nối 2 địa điểm du lịch ~u~ và ~v~ (~u, v \le n; u \ne v~).

Output

• Ghi ra một số là giá trị tối đa của độ chênh lệch chi phí nhỏ nhất tìm được.

Sample Input 1

9 5 4
1 2 3 5 7 4 4 6 8
4 3
5 6
8 9
6 5
3 4

Sample Output 1

3