题目描述

一个国家有 $N$ 座城市和 $M$ 条有向道路，城市编号为 $1$ 到 $N$。第 $i$ 条道路从城市 $a_i$ 通向城市 $b_i$，走完这条道路需要 $c_i$ 分钟。

小婷从城市 $1$ 出发参加限时寻宝活动。活动总时长为 $T$ 分钟，活动结束时她必须回到城市 $1$。在城市 $i$ 停留时，她每分钟可以获得 $A_i$ 枚金币；在道路上行驶的时间不能获得金币。

小婷可以选择任意一座城市作为停留地点，也可以选择城市 $1$。她到达所选城市后，会把除去往返路程之外的全部剩余时间用于收集金币，然后返回城市 $1$。如果某座城市无法在时限内完成往返，就不能选择它。

请计算小婷在 $T$ 分钟内最多能够获得多少枚金币。

输入格式

第一行输入三个整数 $N,M,T$。

第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

接下来 $M$ 行，第 $i$ 行输入三个整数 $a_i,b_i,c_i$，表示一条从 $a_i$ 到 $b_i$、耗时为 $c_i$ 的有向道路。

输出格式

输出一个整数，表示小婷在规定时间内能够获得的最大金币数。

2 2 5
1 3
1 2 2
2 1 1

6

样例说明 #1

前往城市 $2$ 需要 $2$ 分钟，返回需要 $1$ 分钟，剩余 $2$ 分钟可获得 $2\times3=6$ 枚金币。

2 2 3
1 3
1 2 2
2 1 1

3

样例说明 #2

往返城市 $2$ 恰好用完全部时间，无法在那里停留获利，因此留在城市 $1$ 更优。

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

数据范围与约定

$2\le N\le10^5$，$1\le M\le10^5$，$1\le T\le10^9$，$1\le A_i\le10^5$，$1\le c_i\le10^5$。输入中的所有数均为整数。