著名的魔术师博里亚·布迪尼在由 $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。