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 翻译