题目背景

CF1801D

题目描述

著名魔术师博里斯·布迪尼在 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 4 2 0
7 4 3 1
1 2 21
3 2 6
1 3 8
2 4 11

4

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

24

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

提示

样例解释

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

在第二个样例中，布迪尼最优策略是在第一个城市举办 $15$ 场表演，飞到第 $3$ 个城市后再举办 $9$ 场表演，然后前往第 $4$ 个城市。

评分说明

本题测试数据分为 6 组。只有通过某一组的全部测试点，且通过部分之前组的全部测试点后，才能获得该组分数。有些分组不要求通过样例测试点。离线评测表示该组的测试结果会在比赛结束后公布。

组别	分值	$n$	$m$	$s_i$	$w_i$	必须通过的组	备注
0		--	--	--	--	--	样例测试点
1	14				$w_i=1$
2	13		$m = n - 1$		--		$a_i = i$，$b_i = i + 1$
3	17	$n \le 10$	--			0
4	19	$n \le 100$		$s_i \le 100$
5	21			--		0, 3, 4
6	16	--				0--5	离线评测