HD vừa sáng tạo ra một trò chơi điều khiển robot mới cho 2 bé Bi, Bo chơi. Nội dung trò chơi như sau:

• Có ~N~ cây cột đánh số từ 1 đến ~N~, cây cột thứ ~i~ có chiều cao ~h[i]~ (m).
• Có ~M~ đường nhảy dạng ~(i, j, t)~ tương ứng là nhảy từ cây ~i~ sang cây ~j~ (hoặc từ cây ~j~ sang cây ~i~) mất ~t~ (s) và nếu nhảy từ độ cao ~h~ (~h \in \mathbb{N}, h \le h[i]~) của cây ~i~ thì sang cây ~j~ sẽ có độ cao là ~h - t~ với điều kiện ~0 \le h - t \le h[j]~.
• Nếu robot di chuyển lên xuống trên cột hiện tại, thời gian di chuyển mất 1(s) trên 1m di chuyển.

Hiện tại robot đang ở độ cao ~X~ của cây 1, Bi-Bo cần phải tìm phương án di chuyển nhanh nhất đến độ cao ~h[N]~ của cây ~N~.

Yêu cầu: Tính thời gian di chuyển ngắn nhất thỏa mãn yêu cầu đầu bài.

Input

• Dòng 1: Chứa 3 số nguyên dương ~N, M, X~ ~(2 \le N \le 100.000; 1 \le M \le 300.000; 0 \le X \le h[1])~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa 1 số nguyên dương ~h[i]~ ~(1 \le h[i] \le 1.000.000.000)~.
• ~M~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương ~i, j, t~ ~(1 \le t \le 1.000.000.000)~.

Output

• Một số duy nhất là thời gian ngắn nhất để robot di chuyển đến độ cao ~h[N]~ của cây ~N~, nếu không thể di chuyển đến thì ghi -1.

Sample Input 1

5 5 0
50
100
25
30
10
1 2 10
2 5 50
2 4 20
4 3 1
5 4 20

Sample Output 1

110