人类智慧
暂无测试数据。
题面还是简单一点好。
镜华给了你一张有 $n$ 个点 $m$ 条边的有向图，每个点上有点权，不妨认为 $w_i$ 表示第 $i$ 个点上的点权。
同时她还给了你一个计数器 $A$ 以及一个正整数 $T$。
她要求在任意时刻计数器的值都不能小于 $0$ 或者大于 $T$。计数器初始时值为 $0$。
之后你可以在有向图上任意选择一条路径，当你每一次到达一个点 $i$ 的时候，都可以进行以下操作之一：
- 不操作
- 为计数器加上 $w_i$
- 为计数器减去 $w_i$
于是镜华想知道你可以让计数器达到的最大值是多少。
当然了，因为镜华是一个可爱的女孩子，所以她会一次性给你好多张图，也就是说每一个测试点你需要处理多组数据。
输入格式
第一行两个整数 $Task, type$，表示数据组数与当前数据点编号。
你可能并不需要用到 $type$，这时你可以只读入 $type$ 不处理它。
之后会按照如下方式输入 $Task$ 组数据。
第一行三个整数 $n, m, T$。
之后一行 $n$ 个整数，第 $i$ 个整数代表 $w_i$。
之后 $m$ 行，每行两个整数 $a_i,b_i$，表示在 $a_i, b_i$ 之间有一条边。
输出格式
对于每一组数据，输出计数器所能达到的最大值。
数据规模与约定
| 测试点编号 | $n$ | $m$ | $T$ | 特殊性质 |
|---|---|---|---|---|
| $1$ | $\le100$ | $\le500$ | $\le 100$ | 性质 $1$ |
| $2$ | $\le500$ | $\le900$ | $\le 1000$ | 性质 $1$ |
| $3$ | $\le5000$ | $\le20000$ | $\le 10000$ | 性质 $1$ |
| $4$ | $\le5000$ | $\le20000$ | $\le 10000$ | 性质 $1$ |
| $5$ | $\le100$ | $=n$ | $\le 100$ | 性质 $2$ |
| $6$ | $\le5000$ | $=n$ | $\le 10000$ | 性质 $2$ |
| $7$ | $\le5000$ | $=n$ | $\le 10000$ | 性质 $2$ |
| $8$ | $\le5000$ | $\le20000$ | $\le 10000$ | 无 |
| $9$ | $\le5000$ | $\le20000$ | $\le 10000$ | 无 |
| $10$ | $\le5000$ | $\le20000$ | $\le 10000 $ | 无 |
性质 $1$ ： 图中不存在环
性质 $2$ ： 存在一个点 $k(1<k\le n)$，满足 $1$ 到 $k$ 的所有点构成唯一一个环。
对于 $100\%$ 的数据，$1\le n \le 5\times10^3,1\le m \le 2\times10^4,1\le T\le 10^4,1\le w_i\le \frac T 2 $。
保证 $Task \le 5$。
保证图中没有重边与自环。
1 0
6 6 5
2 1 2 1 1 1
4 2
1 2
1 5
2 5
5 3
5 6
5