配点: 100 点
蜜袋鼯的 JOI 你居住的森林里有桉树。 N 这些树上长着树。 它的编号为 1 如果要将其更改为输出最多为 N 。树 i 的高度是 H_i 这是一米。
JOI 有一群树,你可以直接跳到对方身上。 M 有集合,并且每个集合中的树之间跳跃所需的时间是固定的。 JOI 当你在树间跳跃时,距地面的高度是 1 每秒 1 下降几米。也就是说,JOI君现在距离地面的高度是 h 米,在树间跳跃所需的时间 t 秒,跳跃后距地面的高度为 h - t 变为米。然而, 如果高度小于h - t 是 从 0 或大于目标树的高度,则无法跳跃。
此外,JOI 可以通过上下移动树的侧面来增加距地面的高度。 0 可以在米到当前树的高度范围内增加或减少。 JOI你是离地高度 1 增加或减少米 需要 1 秒。
JOI你是一棵树 1 高度 X 米位置的树 N 的顶部(高度 H_N 米)并想知道完成此操作所需的最短时间。
課題
给出了每棵树的高度、JOI可以直接跳转到的树集合信息以及JOI最初所在位置的高度。树 编写一个程序来找出到达 N 顶部所需的最短时间。
入力
从标准输入读取以下数据。
- 1 行包含一个整数 N, M, X 以空格作为分隔符。这意味着树的数量是 N 一本书,一套可移动的树 M 有组,先JOI君 1 高度 X 表示处于米的位置。
- 继续 N 行 i 行目 (1 \leqq i \leqq N) 是一个整数 写入 H_i 。这是一棵树 i 的高度是 H_i 代表米。
- 继续 M 行 j 行目 (1 \leqq j \leqq M) 是一个整数 写入 A_j, B_j, T_j (1 \leqq A_j \leqq N,1 \leqq B_j \leqq N,A_j \neq B_j)以空格作为分隔符。这是一棵树 A_j 和树 B_j 之间相互 这意味着您可以在 T_j 秒内从一个地方跳到另一个地方。另外,1 \leqq j < k \leqq M 然后,(A_j, B_j) \neq (A_k, B_k) 和 (A_j, B_j) \neq (B_k, A_k) 很满意。
出力
该树打印在标准输出上。 1 高度 X 米位置的树 N 是一个整数,表示到达顶部所需的最短时间(以秒为单位)。 输出为 1 行。但是,如果没有这样的方法,而是 输出 -1 。
制限
所有输入数据满足以下条件。
- 2 \leqq N \leqq 100\,000.
- 1 \leqq M \leqq 300\,000.
- 1 \leqq H_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
- 1 \leqq T_j \leqq 1\,000\,000\,000 (1 \leqq j \leqq M).
- 0 \leqq X \leqq H_1.
小課題
小課題 1 [25 点]
满足以下条件。
- N \leqq 1\,000.
- M \leqq 3\,000.
- H_i \leqq 100 (1 \leqq i \leqq N).
- T_j \leqq 100 (1 \leqq j \leqq M).
小課題 2 [25 点]
满足以下条件。
- X = 0.
小課題 3 [50 点]
没有其他限制。
入力例 1
5 5 0 50 100 25 30 10 1 2 10 2 5 50 2 4 20 4 3 1 5 4 20
出力例 1
110
例如,您可以按如下方式移动。
- 木 1 从 50 爬升米。
- 木 1 卡拉树 跳转至 2 。
- 木 2 卡拉树 跳转至 4 。
- 木 4 卡拉树 跳转至 5 。
- 木 5 从 10 爬升米。
入力例 2
2 1 0 1 1 1 2 100
出力例 2
-1
JOI你是一棵树 您无法跳至 1 卡拉树 跳转至 2 。
入力例 3
4 3 30 50 10 20 50 1 2 10 2 3 10 3 4 10
出力例 3
100