题目描述

题目译自 Open Olympiad in Informatics 2023 Day2 T4 「Путь домой」。

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

4 4 2 0
7 4 3 1
1 2 21
3 2 6
1 3 8
2 4 11

4

在第一个样例中，博里亚最优策略是在城市 $1$ 组织 $4$ 次表演，最终拥有 $2 + 7 \cdot 4 = 30$ 卢布，然后沿路线 $1-3-2-4$ 回家，总花费 $6+8+11=25$ 卢布。

4 4 10 0
1 2 10 1
1 2 20
2 4 30
1 3 25
3 4 89

24

在第二个样例中，博里亚最优策略是在城市 $1$ 组织 $15$ 次表演，飞往城市 $3$，在城市 $3$ 再组织 $9$ 次表演，然后前往城市 $4$。

4 4 7 0
5 1 6 2
1 2 5
2 3 10
3 4 50
3 4 70

10

4 1 2 0
1 1 1 1
1 3 2

-1

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。