집으로 가는 길

유명한 마술사 보리 부디는 $n$개의 도시로 이루어진 나라 $X$를 여행하고 있었다. 그런데 불행하게도 1번 도시에서 강도를 당했다. 이제 그는 $n$번 도시에 있는 집까지 먼 길을 가야 한다.

그는 비행기로 이동한다. 나라에는 $m$개의 항공편이 있다. $i$번째 항공편은 $a_i$번 도시에서 $b_i$번 도시로 가며, 요금은 $s_i$이다. 항공편을 타려면 부디가 $a_i$번 도시에 있어야 하고, 손에 최소 $s_i$의 돈이 있어야 한다. 이 돈은 항공권 값으로 쓰인다.

강도를 당한 뒤 그에게는 $p$루블만 남았다. 그래도 그는 포기하지 않는다. $i$번 도시에 있는 동안 그는 매일 공연을 할 수 있고, 공연 한 번마다 $w_i$루블을 번다.

마술사가 집에 갈 수 있는지, 갈 수 있다면 그러기 위해 필요한 공연 횟수의 최솟값이 얼마인지 알아내도록 도와주자.

첫 줄에 네 정수 $n$, $m$, $p$, $g$ ($2 \le n \le 800$, $1 \le m \le 3000$, $0 \le p \le 10^9$, $0 \le g \le 6$)가 주어진다. 각각 도시의 수, 항공편의 수, 처음 가진 돈, 테스트 그룹 번호이다.

둘째 줄에는 $n$개의 정수 $w_1, w_2, \ldots, w_n$ ($1 \le w_i \le 10^9$)이 주어진다. 각 도시에서 공연 한 번으로 얻는 수익이다.

다음 $m$개의 줄에는 각각 세 정수 $a_i$, $b_i$, $s_i$ ($1 \le a_i, b_i \le n$, $1 \le s_i \le 10^9$)가 주어진다. 이는 $i$번째 항공편의 출발 도시, 도착 도시, 요금이다.

부디가 집에 도착하기 위해 필요한 공연 횟수의 최솟값을 정수 하나로 출력한다. 도착할 수 없으면 $-1$을 출력한다.

첫 번째 예제에서 최적의 방법은 1번 도시에서 공연을 4번 하는 것이다. 그러면 부디가 가진 돈은 $2 + 7 \cdot 4 = 30$루블이 된다. 그 뒤 경로 $1-3-2-4$로 날아가면서 $6+8+11=25$루블을 쓴다.

두 번째 예제에서 최적의 방법은 1번 도시에서 공연을 15번 한 뒤 3번 도시로 날아가서 거기서 공연을 9번 하고, 이어서 4번 도시로 가는 것이다.