AT_abc035_d.[ABC035D] トレジャーハント

高桥君居住的国家有 $N$ 个城镇，以及 $M$ 条连接城镇之间的单向道路，每个城镇编号为 $1$ 到 $N$。第 $i$ 条道路允许从 $a_i$ 号城镇移动到 $b_i$ 号城镇，移动需要 $c_i$ 分钟。

高桥君手头没有钱，他决定进行一次持续 $T$ 分钟的寻宝之旅。高桥君在开始的第 $0$ 分钟时位于 $1$ 号城镇，并且在第 $T$ 分钟结束时也必须回到 $1$ 号城镇。如果高桥君在第 $i$ 号城镇停留 $1$ 分钟，他的所持金会增加 $A_i$ 日元。

请你求出在 $T$ 分钟的寻宝之旅中，高桥君所能获得的最大金额。

输入通过标准输入给出，格式如下：

$N$ $M$ $T$
$A_1$ $A_2$ … $A_N$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$
⋮
$a_M$ $b_M$ $c_M$

• 第 $1$ 行包含三个整数，分别表示城镇数、道路数和寻宝的总分钟数 $N, M, T$，满足 $2 \leq N \leq 10^5$，$1 \leq M \leq \min(N(N-1), 10^5)$，$1 \leq T \leq 10^9$。
• 第 $2$ 行包含 $N$ 个整数，第 $i$ 个整数 $A_i$ 表示在第 $i$ 号城镇每停留 $1$ 分钟可以获得的金额，$1 \leq A_i \leq 10^5$。
• 接下来的 $M$ 行，每行包含三个整数 $a_i, b_i, c_i$，表示第 $i$ 条道路的信息：可以从 $a_i$ 号城镇到 $b_i$ 号城镇，花费 $c_i$ 分钟，$1 \leq a_i, b_i \leq N$，$a_i \neq b_i$，$1 \leq c_i \leq 10^5$。
• 对于任意 $i \neq j$，要么 $a_i \neq a_j$，要么 $b_i \neq b_j$。

请输出高桥君通过寻宝所能获得的最大金额。输出一个整数并换行。

部分分

本题设有部分分。

• 对于满足 $1 \leq N \leq 200$ 的数据集，答对可得 $50$ 分。
• 对于没有额外限制的数据集，答对可再得 $50$ 分，总计 $100$ 分。

样例解释 1

• 从第 $0$ 分钟开始，花 $2$ 分钟从 $1$ 号城镇移动到 $2$ 号城镇。
• 从第 $2$ 分钟开始，在 $2$ 号城镇停留 $2$ 分钟，获得 $6$ 日元。
• 从第 $4$ 分钟开始，花 $1$ 分钟从 $2$ 号城镇回到 $1$ 号城镇。
• 第 $5$ 分钟时回到 $1$ 号城镇，寻宝结束。
• 该情况满足部分分的限制。

样例解释 2

• 从第 $0$ 分钟开始，在 $1$ 号城镇停留 $3$ 分钟最优，可获得 $3$ 日元。
• 该情况满足部分分的限制。

样例解释 3

• 该情况满足部分分的限制。

由 ChatGPT 4.1 翻译