测试数据来自 system/1880

背景

窗外斜阳 日暮西山 倚栏眺
想着当年气盛青涩的年少
时光湍急 岁月汹涌 物是人已非
年年我挥汗洒泪赴沙场

描述

Ninian 的魔力可以在结界间传递。
结界中有 N 个光柱，第 i 个光柱的光压范围为 0~Ei 。魔力可以有 M 种传递，从光柱 Ai 传递到光柱 Bi ，花费时间 Ti 。
当魔力从光压为 S 传递并花费了 T 的时间后，就会衰减到光柱上光压为 S-T 处，S-T 不能为负。
Ninian 可以将魔力的光压花费 1 时间增加 1 或减少 1 ，当然魔力的光压不能超过光柱的光压范围，也不能小于 0 。
Ninian 的魔力初始在 1 号光柱，光压为 X 。
问 Ninian 的魔力到达第 N 个光柱且光压最大所需要的最少时间。

格式

输入格式

第一行三个整数 N, M, X 。
接下来的 N 行每行一个整数表示 Ei 。
接下来的 M 行每行三个整数表示 Ai, Bi, Ti 。

输出格式

输出一个整数表示所需的最少时间，如果 Ninian 的魔力无法到达，输出 -1 。

样例1

样例输入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

样例2

样例输入2

2 1 0
1
1
1 2 100

样例输出2

-1

样例3

样例输入3

4 3 30
50
10
20
50
1 2 10
2 3 10
3 4 10

样例输出3

100

限制

2 ≤ N ≤ 100 000．
1 ≤ M ≤ 300 000．
1 ≤ Ei ≤ 1 000 000 000．
1 ≤ Ti ≤ 1 000 000 000．
0 ≤ X ≤ H1．

对于 20% 的数据：
N ≤ 1 000．
M ≤ 3 000．
Hi ≤ 100．
T ≤ 100

对于另外 40% 的数据： X = 0．

提示

样例1解释：
光柱1: 花费 50 时间将光压加到 50 。
1->2->4->5 花费 50 时间，光压=50-50=0
光柱5: 花费 10 时间将光压加到 10 ，达到光柱 5 所能承受最大光压，总花费 110 。

来源

布吉岛。