题目描述

徐老师在玩一个游戏，这个游戏的地图由 $n$ 个点以及 $m$ 条有向边组成

每次到达第 $i$ 个点时，徐老师会获得 $a_i$ 点积分

并且在游戏中有一个限制：在任何时刻积分都必须不小于 $0$ 且不大于 $H$

问徐老师最大能够获得多少积分

本来这个游戏是存在步数限制的，而现在徐老师通过精湛的作弊密码——上上下下左左右右$ABAB$

突破了这个限制，也就是现在徐老师可以在游戏中任意移动，并且徐老师顺手将积分获得规则也进行了修改——现在每次到达第 $i$ 个房间，徐老师可以选择获得 $a_i$ 点积分，或者减去 $a_i$ 点积分，或者让积分不发生变化

徐老师现在想知道，对于输入了作弊码的自己，最大能获得的积分是多少？

输入格式

本题包含多组测试数据，输入第一行包含一个整数 $T$ 表示测试数据数量

对于每组测试数据

第一行包含三个整数 $n,m,H$，含义如题

第二行包含 $n$ 个整数 $a_i$，分别表示每个房间的积分

接下来 $m$ 行，每行包含两个整数 $u_i,v_i$，表示从 $u_i$ 房间出发可以到达 $v_i$ 房间（单向）

输出格式

对于每组测试数据，输出一个整数表示徐老师能获得的最大积分

数据范围

对于 $100$% 的数据， 满足 $1 \le n \le 5 * 10^3,1 \le m \le 2 * 10^4，1 \le H \le 10^4，1 \le a_i \le H/2$。

对于所有数据保证 $T\le 5$ 且图中没有重边与自环

性质 $1$ ： 图中不存在环

性质 $2$ ： 存在一个点 $k(1\le k\le n)$，满足 $1$ 到 $k$ 的所有点构成唯一一个环。

样例输入

3
5 3 11
2 2 2 2 2
1 2
2 3
3 1
6 6 5
2 1 2 1 1 1
4 2
1 2
1 5
2 5
5 3
5 6
5 3 13
4 3 3 3 5
1 2
2 3
3 1

样例输出

10
5
13

样例解释

对于第一组测试数据，选择 $1-2-3-1$ 转圈，即可到达最大值 $10$

对于第二组测试数据，我们可以选择路径$4-2-5-3$，最后计数器值为$5$，可以证明其为计数器能达到的最大值。