진미 여행

도시는 1번부터 $n$번까지 번호가 매겨진 $n$개가 있다. $i$번 도시의 음식은 $c_i$만큼의 행복도를 준다. 도시들은 1번부터 $m$번까지 번호가 매겨진 $m$개의 단방향 도로로 연결되어 있다. $i$번 도로는 도시 $u_i$에서 출발해 도시 $v_i$에서 끝나며, 이 도로를 지나는 데 $w_i$일이 걸린다. $d$일에 도로 $i$를 타고 도시 $u_i$를 떠나면, $d + w_i$일에 도시 $v_i$에 도착한다. W는 $T$일 동안의 여행을 계획한다. 그는 0일에 도시 1을 떠나 $T$일 동안 이동하고, 정확히 $T$일에 도시 1로 돌아와 여행을 마친다. W는 미식가다. 도시에 도착할 때마다, 0일의 도시 1과 $T$일의 도시 1을 포함해, 그곳의 음식을 맛보고 그 도시의 행복도를 얻는다. 같은 도시를 여러 번 방문하면 방문할 때마다 행복도를 얻는다. W는 도시에서 중간에 머물 수 없다. 여행이 끝나기 전에 도시에 도착했다면, 그날 바로 떠나야 한다. 음식 축제가 $K$개 있으며, 각 축제는 서로 다른 시각에 열린다. $i$번째 축제는 $t_i$일에 도시 $x_i$에서 열린다. W가 $t_i$일에 도시 $x_i$에 있으면 추가로 $y_i$만큼의 행복도를 얻는다. W가 여행에서 얻을 수 있는 행복도의 최댓값을 구하라.

첫 줄에는 네 정수 $n$, $m$, $T$, $K$가 주어진다. 각각 도시 수, 도로 수, 여행 기간, 음식 축제 수이다. 둘째 줄에는 $n$개의 정수 $c_1, \ldots, c_n$이 주어진다. 다음 $m$개 줄에는 각각 $u_i$, $v_i$, $w_i$가 주어진다. 마지막 $K$개 줄에는 각각 $t_i$, $x_i$, $y_i$가 주어진다. 데이터는 모든 도로에 대해 $u_i \ne v_i$임을 보장한다. 같은 방향의 평행 도로가 있을 수 있다. 모든 도시에는 출발하는 도로가 적어도 하나 있다. 축제 시각 $t_i$는 모두 다르다.

W가 얻을 수 있는 행복도의 최댓값을 정수 하나로 출력한다. W가 $T$일에 도시 1로 돌아올 수 없다면 -1을 출력한다.

모든 테스트 케이스에 대해 $1 \le n \le 50$, $n \le m \le 501$, $0 \le K \le 200$, $1 \le t_i \le T \le 10^9$, $1 \le w_i \le 5$, $1 \le c_i \le 52501$, $1 \le u_i, v_i, x_i \le n$, $1 \le y_i \le 10^9$이다.