CF1801D The way home

可以在 [P13534](https://www.luogu.com.cn/problem/P13534) 评测本题。

著名魔术师博里斯·布迪尼在 X 国旅行，这个国家共有 $n$ 个城市。不幸的是，他在编号为 $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$。

### 样例解释 在第一个样例中，布迪尼最优策略是在第一个城市举办 $4$ 场表演，此时他共有 $2 + 7 \times 4 = 30$ 卢布，然后依次乘坐 $1 \to 3 \to 2 \to 4$ 的航班，花费 $6 + 8 + 11 = 25$ 卢布。 在第二个样例中，布迪尼最优策略是在第一个城市举办 $15$ 场表演，飞到第 $3$ 个城市后再举办 $9$ 场表演，然后前往第 $4$ 个城市。