题目描述

有 $N$ 个城镇和 $M$ 条单向道路。第 $i$ 条道路从 $a_i$ 到 $b_i$，通过需要 $c_i$ 分钟。

你从 $1$ 号城镇出发，总时间为 $T$ 分钟，并且必须在第 $T$ 分钟时回到 $1$ 号城镇。在城镇 $i$ 停留 $1$ 分钟可以获得 $A_i$ 枚金币。

你可以选择去某个城镇、停留若干分钟再返回。请计算最多能获得多少金币。

输入格式

第一行输入 $N,M,T$。

第二行输入 $A_1,A_2,\ldots,A_N$。

接下来 $M$ 行，每行输入 $a_i,b_i,c_i$。

输出格式

输出一个整数，表示最多能获得的金币数量。

样例

2 2 5
1 3
1 2 2
2 1 1

6

2 2 3
1 3
1 2 2
2 1 1

3

8 15 120
1 2 6 16 1 3 11 9
1 8 1
7 3 14
8 2 13
3 5 4
5 7 5
6 4 1
6 8 17
7 8 5
1 4 2
4 7 1
6 1 3
3 1 10
2 6 5
2 4 12
5 1 30

1488

样例说明

数据范围

• 对于 $50\%$ 的数据，$N\le 200$。
• 对于 $100\%$ 的数据，$2\le N\le 10^5$，$1\le M\le \min(N(N-1),10^5)$，$1\le T\le 10^9$，$1\le A_i\le 10^5$，$1\le c_i\le 10^5$。不存在两条起点和终点都相同的道路。